代码随想录刷题day 4 | 两两交换链表中的节点 19.删除链表的倒数第N个节点 面试题 02.07. 链表相交 142.环形链表II 总结

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

迭代的版本：最重要的就是要知道循环变量怎么取，对于这道题，我们只需要存储需要交换的两个节点的前一个节点即可，只有当这个节点后面有两个节点时才进入循环，其实把握住这一点之后这题就非常容易了。

递归的版本：这道题用递归做简直不要太简单，首先明白递归结束的条件，显然当链表为空或者链表只有一个节点的时候，不需要操作即可。假如列表中有n + 2个节点，其中后n个已经按照要求交换好了，交换好的链表的头用tmp存储。此时，我们只需要把前两个节点交换后并和后面的链表连接起来即可。

上代码

class Solution { // 迭代
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode dummyHead = new ListNode(0, head);
        ListNode pre = dummyHead; 

        while(pre.next != null && pre.next.next != null){ //循环内部就是交换两节点的操作，这个顺序需要注意一下
            ListNode n1 = pre.next, n2 = n1.next;
            n1.next = n2.next;
            n2.next = n1;
            pre.next = n2;
            pre = n1;
        }
        return dummyHead.next;
    }
}

class Solution {  //递归
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode tmp = swapPairs(head.next.next);
        ListNode n2 = head.next, n1 = head;
        n1.next = tmp;
        n2.next = n1;
        return n2;
    }
}

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

链表这些题，为了记忆方便还是都采用dummyHead的做法吧，不是说不能不用，要用就全都用，别搞混了。就和前面数组二分法一样，就左闭右闭，别想别的。要删除一个节点，关键是找到要删除节点的前一个节点，我们可以想到，倒数第n个节点的前一个节点距离倒数第一个节点距离为n。因此，快指针先走n步，随后两个指针一起走，当快指针到达最后一个节点时，慢指针指向的就是倒数第n个节点的前一个节点，此时执行删除操作即可。

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

面试题 02.07. 链表相交

双指针法每次看思路都能看明白，但每次都写不出题解这么清晰简单的流程。实在不行就用HashMap，简单易懂不出错。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null) return null;
        ListNode t1 = headA, t2 = headB;
        while(t1 != t2){
            System.out.println(t1);
            System.out.println(t2);
            t1 = t1 == null ? headB : t1.next;
            t2 = t2 == null ? headA : t2.next;
            
        }
        return t1;
    }
}

142. 环形链表 II

这不纯纯证明题啊，这要是我没见过这个写法，打死也想不到。贴个题解。

说说我的理解吧：这道题的关键就在于理解快慢指针的相遇点距离环入口的距离和从头节点到入口的距离相等。好了，去证明吧（不是）。假设相遇时slow走了a+b步，其中a是从头节点走到入口处的步数，也就是环外节点数目。此时fast走了2 * (a+b)，同时2 * (a+b) == a + nc + b，c是环内节点数。由此可得a+b == nc。所以从相遇点走a步就可以到达环入口（因为走a + nc（a步到入口，nc就是套圈）步就可以到达入口处）。我们不知道a是多少，但此时从头节点再出发一个指针一起走，肯定就会在入口处相遇。

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        while(true){
            if(fast == null || fast.next == null) return null;
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) break;
        }
        fast = head;
        while(fast != slow){
            slow = slow.next;
            fast = fast.next;
        }
        return fast;
    }
}

每天都做点，慢慢也就进步了。不过还是有点畏难情绪，做着做着就偷懒了，慢慢改善吧。