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

链表知识基础

文章链接：https://programmercarl.com/%E9%93%BE%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html#

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

题目链接：https://leetcode.cn/problems/swap-nodes-in-pairs/
使用虚拟头结点，这样会方便很多，要不然每次针对头结点（没有前一个指针指向头结点），还要单独处理。

思路:使用虚拟头结点

设置一个虚拟头结点，这样原链表的所有节点就都可以按照统一的方式进行移除了。
然后注意一下，就是while里面，判断的条件有两个，pre.next != null && pre.next.next != null，才可以交换，也就是后面一个，和后面两个结点都不是null的情况，才可以。同时写的顺序也不能反，否则会报null.next的错误

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;
        while(pre.next != null && pre.next.next != null){
            // ListNode tmp = pre.next.next;
            // pre.next.next = tmp.next;
            // tmp.next = pre.next;
            // pre.next = tmp;
            // pre = pre.next.next;
            ListNode firstNode = pre.next;
            ListNode secondNode = pre.next.next;
            firstNode.next = secondNode.next;
            secondNode.next = pre.next;
            pre.next = secondNode;
            pre = pre.next.next;
        }
        return dummyNode.next;
    }
}

时间复杂度 O(n)

19. 删除链表的倒数第 N 个结点

题目连接：https://leetcode.cn/problems/remove-nth-node-from-end-of-list/description/

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。尝试用一遍扫描实现。

解法：快慢指针

让快指针先移动n步，然后这样再同时移动。
此时快指针移动了size-n步，慢指针也是size-n步，此时慢指针离最后距离也是size-(size-n)=n，也就是题意。
写过一次，有思路就很快了。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        // 快慢双指针
        ListNode slow=dummyNode,fast=dummyNode;
        // 快指针先移动n步
        for(int i=0;i<n;i++)
        {
            fast = fast.next;
        }
        // 然后这个时候，快指针和慢指针，再同时移动。直到快指针移动到最后
        while(fast.next!=null)
        {
            fast = fast.next;
            slow = slow.next;
        }
        // 此时的slow指针指向的是要删除的结点的前一个
        slow.next = slow.next.next;
        return dummyNode.next;
    }
}

时间复杂度O(n)

面试题 02.07. 链表相交

题目连接：https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/

解法：求两个链表交点节点的指针

特别注意！！！交点不是数值相等，而是指针相等。不用比较val，只要比较两个指针是否相等，即可
还有个地方，两个链表的末端一定要先对齐，要不然不满足题意。也就是说，两个链表的指针起始位置是不一样的。一个是在开始处，一个不是。
在这里插入图片描述

/**
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        // 先求两个链表的长度
        int lenA = 0, lenB = 0;
        ListNode curA = headA,curB = headB;
        while(curA!= null)
        {
            curA = curA.next;
            ++lenA;
        }
        while(curB!=null)
        {
            curB = curB.next;
            ++lenB;
        }
        curA = headA;
        curB = headB;
        // 把A确定为更长的
        if(lenA<lenB){
            // 交换结点
            ListNode tmp = curB;
            curB = curA;
            curA = tmp;
            int tmpLen = lenB;
            lenB = lenA;
            lenA = tmpLen;
        }
        // 对齐末端
        int gap = lenA-lenB;
        while(gap-- >0)
        {
            curA = curA.next;
        }
        // 然后这个时候再比较指针是否相同，不是比较val是否相同
        while(lenB-- >0)
        {
            if(curA==curB){
                return curA;
            }
            curA = curA.next;
            curB = curB.next;
        }
        return null;
    }
}

时间复杂度：O(n)

142.环形链表II

题目连接：https://leetcode.cn/problems/linked-list-cycle-ii/

解法1：快慢指针法

主要考察两知识点：
（1）判断链表是否环
（2）如果有环，如何找到这个环的入口

判断链表是否有环

可以使用快慢指针法，分别定义 fast 和 slow 指针，从头结点出发，fast指针每次移动两个节点，slow指针每次移动一个节点，如果 fast 和 slow指针在途中相遇，说明这个链表有环。相对于slow来说，fast是一个节点一个节点的靠近slow的，所以fast一定可以和slow重合。

如果有环，如何找到这个环的入口

假设从头结点到环形入口节点的节点数为x。环形入口节点到 fast指针与slow指针相遇节点节点数为y。从相遇节点再到环形入口节点节点数为 z。如图所示：
在这里插入图片描述
slow指针走过的节点数为: x + y， fast指针走过的节点数：x + y + n (y + z)，n为fast指针在环内走了n圈才遇到slow指针，（y+z）为一圈内节点的个数A。
（slow指针肯定是走了一圈不到的，因为他俩的速度差在一圈内是完全追的上的）

因为fast指针是一步走两个节点，slow指针一步走一个节点，所以 fast指针走过的节点数 = slow指针走过的节点数 * 2：

(x + y) * 2 = x + y + n (y + z)

两边消掉一个（x+y）: x + y = n (y + z)

因为要找环形的入口，那么要求的是x，因为x表示头结点到环形入口节点的的距离。

所以要求x ，将x单独放在左面：x = n (y + z) - y ,

再从n(y+z)中提出一个（y+z）来，整理公式之后为如下公式：x = (n - 1) (y + z) + z 注意这里n一定是大于等于1的，因为 fast指针至少要多走一圈才能相遇slow指针。

这个公式说明什么呢？

先拿n为1的情况来举例，意味着fast指针在环形里转了一圈之后，就遇到了 slow指针了。

当 n为1的时候，公式就化解为 x = z，

这就意味着，从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点，那么当这两个指针相遇的时候就是环形入口的节点。

也就是在相遇节点处，定义一个指针index1，在头结点处定一个指针index2。

让index1和index2同时移动，每次移动一个节点，那么他们相遇的地方就是环形入口的节点。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 方法2:快慢指针
        ListNode slowIndex = head,fastIndex = head;
        while(fastIndex!=null && fastIndex.next != null){
            // 快指针一次移动两格，慢指针一次移动一格
            fastIndex = fastIndex.next.next;
            slowIndex = slowIndex.next;
            // 有环的情况
            if(slowIndex == fastIndex){
                // 相交的点
                ListNode joint = slowIndex;
                ListNode startNode = head;
                // 需要数学证明！
                // 从头结点出发一个指针，从相遇节点也出发一个指针，这两个指针每次只走一个节点， 
                // 那么当这两个指针相遇的时候就是 环形入口的节点。
                while(startNode!=joint){
                    joint = joint.next;
                    startNode = startNode.next;
                }
                return joint;
            }
        }
        return null;

    }
}

时间复杂度：O(n)
空间复杂度：O(1)

解法2：哈希法

一种非常直观的解法，我们遍历链表中的每个节点，并将它记录下来；一旦遇到了此前遍历过的节点，就可以判定链表中存在环。借助哈希表可以很方便地实现。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode detectCycle(ListNode head) {
        // 方法1：哈希表的方式
        ListNode cur = head;
        HashSet<ListNode>nodes = new HashSet<ListNode>();
        while(cur!=null){
            if(nodes.contains(cur))
                return cur;
            else
                nodes.add(cur);
            cur = cur.next;
        }
        return null;
    }
}