前言：
先前我們在鏈表的單元已經介紹過求鏈表中點的「前後指針」與求有環鏈表的「快慢指針」，這都是雙指針的應用。
在接下來的這個章節，主要會介紹的雙指針應用，與更進階的滑動窗口(sliding window)的應用。

一、Two Pointer in LinkedList

  • 在本文中會學到 LinkedList 的七種技巧：
    1. 合併兩個有序鏈表
    2. 分解鏈表
    3. 合併多個有序鏈表
    4. 尋找鏈表的倒數第 k 個節點
    5. 尋找鏈表的中點
    6. 判斷鏈表是否包含環
    7. 判斷兩個鏈表是否相交

1. Merge Two Sorted Lists

  • Leetcode 21. Merge Two Sorted Lists ex1-1
  • 這一題的小技巧是創建一個 dummy node 依序將兩條鏈表中較小的值接在後面，最後回傳 dummy->next，過程很像 merge sort。
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode* dummy = new ListNode();
    ListNode* curr = dummy;
    while (list1 && list2) {
        if (list1->val <= list2->val) {
            curr->next = list1;
            list1 = list1->next;
        } else {
            curr->next = list2;
            list2 = list2->next;
        }
        curr = curr->next;
    }
    if (list1) curr->next = list1;
    if (list2) curr->next = list2;
    return dummy->next;
}

二、Two Pointer in Array

三、Sliding Window