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

思路：一开始思路方向错误了，想着需要翻转列表，卡了好久，还导致链表内成环。其实画图看每个节点的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;
        while(cur != null && cur.next != null && cur.next.next != null){
            ListNode temp1 = cur.next;
            ListNode temp2 = cur.next.next;
            ListNode temp3 = cur.next.next.next;
            cur.next = temp2;
            temp2.next = temp1;
            temp1.next = temp3;

            cur = temp1;
        }
        return dummy.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 prev = dummy;
        ListNode cur = head;
        while(cur != null && cur.next != null){
            ListNode temp = cur.next.next;
            prev.next = cur.next;
            prev.next.next = cur;
            cur.next = temp;
            prev = cur;
            cur = temp;
        }
        return dummy.next;
    }
}

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

使用两趟扫描实现，第一趟求链表长度，第二趟才进行删除。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        int sz = 0;
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        ListNode cur = head;
        while(cur != null){
            sz++;
            cur = cur.next;
        }
        //System.out.println("sz: " + sz);
        cur = dummy;
        if(n == sz)
            return head.next;
        for(int i = 0; i < sz - n; i++){
            cur = cur.next;
        }
        cur.next = cur.next.next;
        return dummy.next;
    }
}

通过快慢指针实现一趟删除：

fast首先走n + 1步，同时移动的时候slow才能指向删除节点的上一个节点
fast和slow同时移动，直到fast指向末尾

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head;
        // fast先走(n+1)步，那样等fast到null的时候，slow就到要删除的节点的上一个节点
        while(n-- > 0){
            fast = fast.next;
        }
        if(fast == null)
            return head.next;
        fast = fast.next;
        ListNode slow = head;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

?LeetCode?面试题 02.07. 链表相交

重点：交点不是数值相等，而是指针相等！

思路：

考虑构建两个节点指针?A??,?B?分别指向两链表头节点?headA?,?headB
指针?A?先遍历完链表?headA?，再开始遍历链表?headB
指针?B?先遍历完链表?headB?，再开始遍历链表?headA
若两链表有公共尾部：指针?A?,?B?同时指向「第一个公共节点」node
若两链表无：指针?A?,?B?同时指向?null

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if(headA == null || headB == null){
            return null;
        }
        ListNode curA = headA;
        ListNode curB = headB;
        Boolean isLinked = false;
        while(curA != null || isLinked == false){
            if(curA == curB)
                break;
            if(curA.next == null && isLinked == false){
                isLinked = true;
                curA = headB;
            }else{
                curA = curA.next;
            }
            if(curB.next == null){
                curB = headA;  
            }else{
                curB = curB.next;
            }           
        }
        return curA;
    }
}

?LeetCode?环形链表II?

思路：设两指针?fast，slow?指向链表头部?head，fast?每轮走2步，slow?每轮走1步

根据：

f=2s? (快指针每次2步，路程刚好2倍）
f = s + nb (相遇时，刚好多走了n圈）

推出：s = nb

从head结点走到入环点需要走： a + nb，而slow已经走了nb，那么slow再走a步就是入环点了。

如何知道slow刚好走了a步？从head开始，和slow指针一起走，相遇时刚好就是a步

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