24. 兩兩交換鏈表中的節(jié)點

https://leetcode.cn/problems/swap-nodes-in-pairs/description/
一道模擬題，我的第一版解法

// 雙指針不斷移動，交換數(shù)據(jù)
class Solution {
    public ListNode swapPairs(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode left = head;
        ListNode right = head.next;
        ListNode preRight = null;
        head = right;
        while (left != null && right != null) {
            ListNode tmp = right.next;
            left.next = tmp;
            right.next = left;
            if (preRight != null) {
                preRight.next = right;
            }
            if (tmp == null) {
                break;
            } else {
                preRight = left;
                left = tmp;
                right = tmp.next;
            }
        }
        return head;
    }
}

卡哥更簡潔的解法

class Solution {
  public ListNode swapPairs(ListNode head) {
        ListNode dumyhead = new ListNode(-1); // 設置一個虛擬頭結(jié)點
        dumyhead.next = head; // 將虛擬頭結(jié)點指向head，這樣方便后面做刪除操作
        ListNode cur = dumyhead;
        ListNode temp; // 臨時節(jié)點，保存兩個節(jié)點后面的節(jié)點
        ListNode firstnode; // 臨時節(jié)點，保存兩個節(jié)點之中的第一個節(jié)點
        ListNode secondnode; // 臨時節(jié)點，保存兩個節(jié)點之中的第二個節(jié)點
        while (cur.next != null && cur.next.next != null) {
            temp = cur.next.next.next;
            firstnode = cur.next;
            secondnode = cur.next.next;
            cur.next = secondnode;       // 步驟一
            secondnode.next = firstnode; // 步驟二
            firstnode.next = temp;      // 步驟三
            cur = firstnode; // cur移動，準備下一輪交換
        }
        return dumyhead.next;  
    }
}

題后感：
1.和卡哥的解法邏輯上是一致的，但我的代碼不夠簡潔
2.鏈表題一定要畫圖，否則很容易繞暈
3.學會使用虛擬節(jié)點方法，在鏈表題中卡哥基本都用到了

19.刪除鏈表的倒數(shù)第N個節(jié)點

https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
該題用非常高頻使用的快慢指針的解法，比較簡單

// 第一版解法 - 沒有使用虛擬節(jié)點，需要處理只有一個元素的邊界情況
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if (n <= 0) {
            return head;
        }
        if (head.next == null && n == 1) {
            head = null;
            return head;
        }
        ListNode slow = head;
        ListNode fast = head;
        // 快走n步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        // 開始移動判斷,快指針不是最后一個元素
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 刪除元素
        slow.next = slow.next.next;
        return head;
    }
}
// 第二版解法 - 使用虛擬節(jié)點
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fakeNode = new ListNode(0);
        fakeNode.next = head;

        ListNode slow = fakeNode;
        ListNode fast = fakeNode;
        // 快走n步
        for (int i = 0; i <= n; i++) {
            fast = fast.next;
        }
        // 開始移動判斷,快指針不是最后一個元素
        while(fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        // 刪除元素
        slow.next = slow.next.next;
        // !!!!注意最后返回值
        return fakeNode.next;
    }
}

面試題 02.07. 鏈表相交

同 https://leetcode.cn/problems/intersection-of-two-linked-lists-lcci/description/

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lenA = 0;
        int lenB = 0;
        ListNode curA = headA;
        ListNode curB = headB;
        while (curA != null) {
            lenA++;
            curA = curA.next;
        }
        while (curB!= null) {
            lenB++;
            curB = curB.next;
        }
        curA = headA;
        curB = headB;
        int step = 0;
        if (lenA - lenB >= 0) {
            step = lenA - lenB;          
        } else {
            step = lenB - lenA;
            curA = headB;
            curB = headA;
        }
        while(step > 0) {
            curA = curA.next;
            step--;
        }

        while (curA != null && curB != null) {
            if (curA == curB) {
                return curA;
            } 
            curA = curA.next;
            curB = curB.next;
        }

        return null; 
    }
}

這道題剛開始沒想到先計算長度差、長鏈表快走n步的方法，也想了很久，知道解法就好做?？右采?。代碼邏輯基本一致。

142.環(huán)形鏈表II

https://leetcode.cn/problems/linked-list-cycle-ii/description/
判斷是否有環(huán)，如果有環(huán)，返回入環(huán)的第一個節(jié)點
(若干年前畢業(yè)找工作的時候《劍指offer》里看到過？)

// 看完解法之后的版本
public class Solution {
    public ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) {
            return null;
        }
        // 判斷是否有環(huán)
        ListNode slow = head;
        ListNode fast = head;
        ListNode seeNode = null;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                seeNode = slow;
                break;
            }
        }
        // 找環(huán)入口
        if (seeNode == null) {
            return null;
        }
        ListNode tmpNode = head;
        while (tmpNode != null) {
            if (tmpNode == seeNode) {
                return tmpNode;
            }
            tmpNode = tmpNode.next;
            seeNode = seeNode.next;
        }

        return null;
    }
}
// 卡哥簡潔版
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) {// 有環(huán)
                ListNode index1 = fast;
                ListNode index2 = head;
                // 兩個指針，從頭結(jié)點和相遇結(jié)點，各走一步，直到相遇，相遇點即為環(huán)入口
                while (index1 != index2) {
                    index1 = index1.next;
                    index2 = index2.next;
                }
                return index1;
            }
        }
        return null;
    }
}

題后感
1.快慢指針檢測有環(huán)這個解法是之前就知道的，但是求入口環(huán)不知道，沒想到還要列公式，不知道實際面試的時候難道還得自己推導一遍嗎？
2.自己看完題的解法之后第一個版本問題在判斷是否有環(huán)的條件上
初始化時，對slow及fast的賦值是在外面還是在里面，如果在while之外初始化的時候就賦值，那需要單獨判斷next的有效性，while條件里也要判斷，這個時候就有重復了，不簡潔