|
代码随想录
[注：题目来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/minimum-size-subarray-sum]
目录
24. 两两交换链表中的节点
19.删除链表的倒数第N个节点
面试题 02.07. 链表相交
142.环形链表II
一刷今天的链表作业收获还是很多的，特别是从链表相交和环形链表里学到了不少知识。
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
看到这道题直接就修改节点值ac了，然后再一看题目才发现不能这样...
之后重新捋了一下思路，开始是准备一步全换到位，后面想了想不太现实。后面就将整个链表的更换换成简化成两个两个的依次更换，需要注意的就是，当前指针必须指向需要交换的两个节点的前一个节点。（这也是链表操作中的核心，指针必须指向被操作节点的前一个节点，因为被操作节点的地址存在上一个节点中！！！）同时需要注意，链表中对节点的操作，有时需要将操作前的地址临时存起来，避免后续链表节点无法访问到。
/**
* 24. 两两交换链表中的节点
* @param head 给你一个链表，两两交换其中相邻的节点
* @return 返回交换后链表的头节点
*/
public ListNode swapPairs1(ListNode head) {
//输入：head = [1,2,3,4] 输出：[2,1,4,3]
ListNode dummyNode = new ListNode(-1, head);
ListNode cur = dummyNode;
ListNode tempNode1;
ListNode tempNode2;
// 一开始没思路是因为想一口吃成胖子，想一下子把所有的都操作完....有点离谱，以后分析问题需要注意先由大化小，先解决小的，再解决大的！
while (cur.next != null && cur.next.next != null){// 这里循环结束考虑到链表长度可能是奇数或者是偶数，注意二者顺序不能调换，调换可能存在cur.next == null,则cur.next.next就会报空指针异常！！！
tempNode1 = cur.next;
tempNode2 = cur.next.next.next;
cur.next = cur.next.next;
cur.next.next = tempNode1;
cur.next.next.next = tempNode2;
cur = cur.next.next;
}
return dummyNode.next;
}
?看到还有更简单的递归方法，二刷时补上。
给你一个链表，删除链表的倒数第?n?个结点，并且返回链表的头结点。
一开始没什么思路，然后看作业提示是双指针的操作，就摸索了一会，没想到ac了，挺开心的。这里核心还是当前的cur指针必须指向删除节点的前一个节点，一个快指针遍历链表，慢指针去删除节点，快慢指针的初始间隔就是n。
为什么是n呢？这里举个例子：
head = [1,2,3,4,5], n = 2
添加完虚拟头节点后：
dummy，? ? ? ? 1，? ? ? ? 2，? ? ? ? 3，? ? ? ? 4，? ? ? ? 5，? ? ? ? null
????????????????????????????????????????????????cur? ? ? ? ? ? ? ? ? ? ? ? fast? ? ? ? ? ? ?
可以看到，要删除4，当前节点就需要指向3，而3节点与尾节点的距离恰好是2。? 分析发现n>2时适用以上情况，n=1时需要单独讨论。? ? ? ? ? ? ? ? ? ? ?
/**
* 19. 删除链表的倒数第 N 个结点
* @param head 给你一个链表
* @param n 删除链表的倒数第 n 个结点
* @return 返回链表的头结点。
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// 输入：head = [1,2,3,4,5], n = 2 输出：[1,2,3,5]
ListNode dummyNode = new ListNode(-1, head);
ListNode cur = dummyNode;
ListNode fast = dummyNode;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
while (fast.next != null){//循环结束的条件是快指针下一个节点为null
cur = cur.next;
fast = fast.next;
}
if (n == 1){
cur.next = null;
return dummyNode.next;
}
cur.next = cur.next.next;//这里不会报空指针异常，因为右边指向的位置<=fast指向的位置！
return dummyNode.next;
}
这道题没什么思路，看了答案讲解，这里就不做记录，留个位置二刷补上。
这道题是一点思路都没有，也是直接看了讲解，现在感觉对确定链表存在环和找到环入口的方法有了一定的了解，不敲代码，留二刷时补上。
|