代码随想录算法训练营第 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;     //1
    ListNode cur = dummy;
    ListNode slow, fast;

    while(cur.next != null && cur.next.next != null){ //3

      //在这里用cur同时定位slow和fast的相对位置   //2
      slow = 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);  //1
        
        ListNode fast = dummy, slow = dummy;

        for(int i=0; i<=n; i++){    //2
            fast = fast.next;
        }
      
        while(fast!=null){  //3
            fast = 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;   //1

        ListNode dummy = new ListNode(-1, head);
        
        ListNode fast = dummy, slow = dummy;

        for(int i=0; i<=n; i++){
            fast = fast.next;
        }
      
        while(fast.next!=null){   //2
            fast = 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

讲解：代码随想录