代码随想录算法训练营第 4 天（链表 2）| 24. 两两交换链表中的节点19.删除链表的倒数第N个节点 -

一、24. 两两交换链表中的节点

题目：24. 两两交换链表中的节点 - 力扣（LeetCode）

视频：帮你把链表细节学清楚！ | LeetCode：24. 两两交换链表中的节点_哔哩哔哩_bilibili

讲解：代码随想录

dummy->1->2->3->

注意操作的顺序：

① dummy->2

② 2->1

③ 1->3

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode dummy = new ListNode(-1);dummy.next = head;     //1ListNode cur = dummy;ListNode slow, fast;while(cur.next != null && cur.next.next != null){ //3//在这里用cur同时定位slow和fast的相对位置   //2slow = cur.next;fast = slow.next.next;cur.next = slow.next;cur.next.next = slow;slow.next = fast;cur = slow;}return dummy.next;}
}

注意：

1、定义完虚拟头结点之后，记得连在头结点之前；

2、fast 和 slow 指针放在循环中，用cur同时定位slow和fast的相对位置，省了每次定位 fs 两个指针的代码；

3、这里不能写成 ||，因为写成 || 节点是奇数个就无法判断到后面的条件

只要 cur.next 或 cur.next.next 中有一个不为 null，循环就会继续。这意味着即使 cur.next为 null，只要 cur.next.next不为 null，循环仍然会继续，这会导致 NullPointerException，因为你试图访问 null 的 next属性。

尝试过程：

class Solution {public ListNode swapPairs(ListNode head) {if(head == null || head.next == null) return head;ListNode dummy = new ListNode(-1);dummy.next = head;   //ListNode cur = dummy;ListNode slow = head;ListNode fast = head.next.next;while(cur.next != null || slow.next != null){cur.next = slow.next;cur.next.next = slow;slow.next = fast;cur = slow;slow = fast;fast = slow.next.next;    //这里有问题}return dummy.next;}
}

在处理链表成对交换时存在一些逻辑问题，特别是在更新fast指针和处理链表末尾的部分，报了空指针异常。

解决办法是：把 fast 和 slow 指针放在循环里改变

二、19.删除链表的倒数第N个节点

题目：19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）

视频：链表遍历学清楚！ | LeetCode：19.删除链表倒数第N个节点_哔哩哔哩_bilibili

讲解：代码随想录

双指针的经典应用

思路： 如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(head == null) return null;ListNode dummy = new ListNode(-1, head);  //1ListNode fast = dummy, slow = dummy;for(int i=0; i<=n; i++){    //2fast = fast.next;}while(fast!=null){  //3fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;        }
}

注意：

1、接在 head 之前用这一步写就行： 初始化一个空结点，初始赋值为0，并且list的下一个next指针指向head，指针指向为list： ListNode list=new ListNode(0,head);

2、注意终止条件，如果是 i<=n，加上=，slow 指针到时可以刚好停在删除元素的前一个节点

3、终止条件是 fast 判空，不是 fast.next 判空

尝试过程：

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(head == null) return -1;   //1ListNode dummy = new ListNode(-1, head);ListNode fast = dummy, slow = dummy;for(int i=0; i<=n; i++){fast = fast.next;}while(fast.next!=null){   //2fast = fast.next;slow = slow.next;}slow.next = slow.next.next;return dummy.next;}
}

1、返回值类型错误：如果链表为空，应该返回null而不是-1，因为-1不是一个有效的链表节点。

2、见上面

三、面试题 02.07. 链表相交

同：160.链表相交

题目：面试题 02.07. 链表相交 - 力扣（LeetCode）

视频：

讲解：代码随想录

四、142.环形链表II

题目：142. 环形链表 II - 力扣（LeetCode）

视频：把环形链表讲清楚！ 如何判断环形链表？如何找到环形链表的入口？ LeetCode：142.环形链表II_哔哩哔哩_bilibili

讲解：代码随想录