代码随想录算法训练营Day4 | 24.两两交换链表中的节点、19.删除链表的倒数第 N 个节点、面试题. 链表相交、142.环形链表II

LeetCode 24 两两交换链表中的节点

本题要注意的条件：

1. 遍历终止条件
2. 改变引用指向的时候，需要保存一些节点记录

为了更好的操作链表，我定义了一个虚拟的头节点 dummyHead 指向链表。如下图所示

• 既然要交换链表中的节点，那么肯定需要有遍历的指针 cur，还有保存节点 前驱或者后继的节点 tmp。下面通过以下几个图来讲述代码的一个整体思路
• 后续就是重复以上步骤，那么还有没解决的问题就是，这个循环的终止条件是什么？我们继续来分析一下
  所以终止条件 while(cur.next != null && cur.next.next != null)

注意点：

1. 不能写成 while(cur.next.next && null cur.next != null ) 如果是偶数个节点的话，此时就会出现空指针异常的情况。
2. 也不能写成 while(cur.next != null || cur.next.next != null)，也会出现空指针异常，当 节点为偶数个时候，那么 cur.next = null ,不满足就判断第二个条件，此时 cur.next.next就会出现空指针异常，因为 cur.next = null

---

LeetCode 19 删除链表的倒数第N个节点

本题思路：

• 要删除倒数第 N 个节点的话，我们要找到倒数第 N 个节点的前驱节点，也就是我们要知道正数是第几个。下面用一个图来描述下思路
• 所以第一步就是定义一个计数器，遍历链表，得到节点总个数 size，然后得出 index = size - n。然后定义个 tmp 指针往后遍历 index 次，指向 index 下标节点，然后改变指针指向即可。
• 最后返回 dummyHead.next

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 使用一个虚拟头节点好操作一点
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode tmp = dummyHead;
        ListNode cur = head;
        int size = 0;
        while(cur != null){
            size++;
            cur = cur.next;
        }
        int index = size - n;
        while(index-- != 0){
            tmp = tmp.next;
        }
        tmp.next = tmp.next.next;
        return dummyHead.next;
    }  
}

---

LeetCode 面试题 0207 链表相交

本题注意点： 值相同，但不一定节点是同一个

本题思路:

1. 首先我们需要往后遍历，但是两个链表长度不一样，所以要让两个链表长度一样，就要先遍历两个链表，得到 A 和 B 链表的长度，然后长度大的遍历两个链表长度差值，让两个链表的长度相等。
2. 只有这样我们往后遍历的时候，才能对比链表的值是否相等，节点是否同一个。否则直接开始遍历，永远也匹配不到
   

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 首先遍历两个链表，算出长度
        int sizeA = 0;
        int sizeB = 0;
        ListNode A = headA;
        ListNode B = headB;
        while(A != null){
            sizeA++;
            A = A.next;
        }
        while(B != null){
            sizeB++;
            B = B.next;
        }
        int res = Math.abs(sizeA-sizeB);
        if( sizeA > sizeB){
            while(res-- != 0){
                headA = headA.next;
            }
        }else{
            while(res-- != 0){
                headB = headB.next;
            }
        }

        // 此时 两个链表长度相等，就可以开始同时遍历
        while(headA != null){
            if(headA.val == headB.val && headA == headB){
                return headA;
            }
            headA = headA.next;
            headB = headB.next;
        }
        return headA;
    }
}

---

LeetCode 142 环形链表||

本题思路：使用快慢指针来解决这道题，下面来详细介绍下这个思想

看完上图，大家可能有以下几个疑问？

• slow 为什么不可以是 slow = x + n (y + z)，下面用一个图来描述
• 为什么 x = n (y + z) - y，n 一定是大于等于1 ，如果为 0 的话，这是不可能出现的情况，看下图：

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null){
            slow = slow.next;
            fast = fast.next.next;
            // 如果两个相遇了说明有环
            if(slow == fast){
                ListNode meet = fast;
                ListNode start =  head;
                while( meet != start){
                    meet = meet.next;
                    start = start.next;
                }
                return meet;
            }
        }
        return null;
    }
}