代码随想录第十二期训练营-第四天

今天的任务是力扣24、19、面试题02.07、力扣142，今天的昨晚这周任务结束，完成代码随想录数组和链表两部分。

***************

这题就是模拟题，必须画图，不画图太难想。还是要用虚拟头节点这个方法，思路会比较清晰。

比如链表为1->2->3->4，cur指向虚拟头节点，交换的过程就是cur指向2，2指向1，1指向3，然后cur到1的位置，就这么四步。无非就是cur.next和cur.next.next来回指。

有几个注意的点：

链表长度可能为奇数也可能为偶数，所以cur指针遍历链表的时候，while的循环条件就要注意一下，如果为偶数，

cur.next != null。如果为奇数，cur.next.next != null。

交换的过程要设置临时变量temp，先用来记录下一次cur的位置，要不然你更改了一个节点的Node之后就找不到原来的

next了。最好是再用两个变量firstNode和secondNode记录cur.next以及cur.next.next，这样更清晰。

class Solution {
    public ListNode swapPairs(ListNode head) {
        
        ListNode dummyHead = new ListNode(-1,head);
        ListNode cur = dummyHead;
        ListNode firstNode;
        ListNode secondNode;
        while(cur.next != null && cur.next.next != null){
             ListNode temp = cur.next.next.next;
             firstNode = cur.next;
             secondNode = cur.next.next;
             cur.next = secondNode;
             secondNode.next = firstNode;
             firstNode.next = temp;
             cur = firstNode;
        }

        return dummyHead.next;
    }
}

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

这题用双指针，双指针应用于链表的删除题是有固定套路的。假如要删除的元素是倒数第二个，n = 2。还是先设置虚拟头节点，快慢指针都从虚拟头节点出发，fast指针先移动n+1次，到达被删元素的前一个节点，然后让slow和fast一起移动，当fast除了链表到了null之后，slow的位置就是被删元素的前一个节点。

面试题 02.07. 链表相交

这是一道经典面试题，一般情况下两个链表长度不相等，我们需要让两个链表尾部对其，从同一个起点出发（也就是短链表的头节点对应的位置），开始遍历找交点。那程序中怎么模拟尾部对起呢，其实就是知道两个链表长度的差，比如差为1，那就让长链表从索引为1的节点开始遍历即可。要注意的是，程序中我们怎么知道谁长谁短，就假设A链表长，即使补偿，就交换长度以及头节点，让A变成长链表就行了。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode nodeA = headA;
        ListNode nodeB = headB;

        int lenA = 0;
        int lenB = 0;

        while(nodeA != null){
            nodeA = nodeA.next;
            lenA++;
        }
        while(nodeB != null){
            nodeB = nodeB.next;
            lenB++;
        }

        nodeA = headA;
        nodeB = headB;

        //就认为A为长链表，就算A是短的也交换
        //找到长链表
        if(lenB > lenA){
            int tempInt = lenA;
            lenA = lenB;
            lenB = tempInt;
            ListNode temp = nodeA;
            nodeA = nodeB;
            nodeB = temp;
        }

        //求出长度差
        int sub = lenA - lenB;
        //移动指针让尾部对齐
        while(sub-- > 0){
            nodeA = nodeA.next;
        }

        //找交点
        while(nodeA != null){
            if(nodeA == nodeB){
                return nodeA;
            }
            nodeA = nodeA.next;
            nodeB = nodeB.next;
        }

        return null;

    }
}

142.环形链表

这题挺重要，能扩展。最简单的情况就是判断是否成环，进阶就是如果有环，入口在哪。

双指针思想，fast一次移动两个，slow一次移动一个。fast一定先入环，然后slow进入，fast去追slow，有环就一定追上，就跟高中数学追击问题一样。这里可以想一个问题，为什么一定能追上呢？因为fast相对于slow一次只移动一个节点，这么一个一个的移动一定会追上而不会越过。

之后就是找环入口问题，怎么找，需要一点小小的公式推导，截个图先，代码随想录里的。

二者相遇时，slow走的节点数为x+y，fast走的节点数为x+y+n(y+z)，n代表走了n圈。fast是slow速度的2倍，所以2(x+y) = x+y+n(y+z)。一顿操作变换，最后就是x = (n - 1) (y + z) + z，代码随想录里有的。这个意思就是，有一个指针从起点出发，走到环入口时，另一个指针从相遇点出发，已经走了n-1圈并加z。这里的n-1一圈根本不重要，主要就是两个指针分别从起点出发和快慢指针相遇点出发后，相遇时就是在环的入口。

这里说一下为什么slow到相遇点时走的为x+y，而不是已经走了若干环再加y呢？引用代码随想录中的一张图。