1.合并兩個(gè)排序的鏈表：迭代
輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
    ListNode dummy=new ListNode(0);     // 弄一個(gè)頭節(jié)點(diǎn)
    ListNode r=dummy;                   // 記錄頭節(jié)點(diǎn)巢寡，最后返回的時(shí)候使用
    while(l1!=null&&l2!=null){
        if(l1.val<=l2.val){
            r.next=l1;
            l1=l1.next;
        } else{
            r.next=l2;
            l2=l2.next;

        }
        r=r.next;
    }
    r.next=l1==null?l2:l1;
    return dummy.next;
}

2.反轉(zhuǎn)鏈表：遞歸

直接用遞歸方法，不然很麻煩僚纷；遞歸都有一個(gè)base闷盔，就是終止條件

1->2->3->4
// 反轉(zhuǎn)得到p
     p
1->2<-3<-4
 <-
把p的節(jié)點(diǎn)指向head潜的，然后把head釋放掉

// 遞歸，時(shí)間空間都是o(n)
public ListNode reverseList(ListNode head) {
    if(head==null||head.next==null){
        return head;
    }
    ListNode p=reverseList(head.next);
    head.next.next=head;
    head.next=null;
    return p;
}

// 非遞歸,時(shí)間o(n),空間o(1)
ListNode* reverseList(ListNode* head) {
        ListNode *pre=NULL;
        ListNode *next=NULL;
        if(head==NULL) return NULL;
        while(head->next){
        next=head->next;
        head->next=pre;
        pre=head;
        head=next;
        }
        head->next=pre;
        return head;
    }

3.反轉(zhuǎn)從位置 m 到 n 的鏈表：遞歸

// 迭代
// 1->2->3->4->5->6. m=2, n=5
// 1->3->2->4->5->6
// 1->4->3->2->5->6
// 1->5->4->3->2->6
      ListNode* reverseBetween(ListNode* head, int m, int n) {
        ListNode* dummpy = new ListNode(-1);
        dummpy->next = head;
        ListNode* pre = dummpy;
        for (int i = 0; i < m - 1; i++) {
            pre = pre->next;
        }
        ListNode* cur = pre->next;
        for (int i = m; i < n; i++) {
            ListNode* next = cur->next;
            cur->next = next->next;
            next->next = pre->next;
            pre->next = next;
        }
        return dummpy->next;
    }


//*************遞歸************
public ListNode reverseBetween(ListNode head, int m, int n) {
    if(m==1){//從第一個(gè)位置開(kāi)始谨敛，即返回前n個(gè)
        return reverseList(head,n);
    }
    head.next=reverseBetween(head.next,m-1,n-1);
    return head;
}

private ListNode successor;

//反轉(zhuǎn)前n個(gè)元素
public ListNode reverseList(ListNode head, int n) {
    if(n==1){
        successor=head.next;//記錄后繼結(jié)點(diǎn)
        return head;
    }
    ListNode p=reverseList(head.next,n-1);
    head.next.next=head;
    head.next=successor;//將head指向后繼跨嘉，反轉(zhuǎn)整條鏈表尾null
    return p;
}

4.K個(gè)一組反轉(zhuǎn)鏈表：迭代
k 是一個(gè)正整數(shù)尊蚁，它的值小于或等于鏈表的長(zhǎng)度亡笑。
如果節(jié)點(diǎn)總數(shù)不是 k 的整數(shù)倍，那么請(qǐng)將最后剩余的節(jié)點(diǎn)保持原有順序横朋。
示例：
給你這個(gè)鏈表：1->2->3->4->5
當(dāng) k = 2 時(shí)邦蜜，應(yīng)當(dāng)返回: 2->1->4->3->5
當(dāng) k = 3 時(shí)翁逞，應(yīng)當(dāng)返回: 3->2->1->4->5

// *************第一種**********
ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode *dummy = new ListNode(-1), *pre = dummy, *cur = pre;
        dummy->next = head;
        int num = 0;
        while (cur = cur->next) ++num;
        while (num >= k) {
            cur = pre->next;
            for (int i = 1; i < k; ++i) {
                ListNode *next = cur->next;
                cur->next = next->next;
                next->next = pre->next;
                pre->next = next;
            }
            pre = cur;
            num -= k;
        }
        return dummy->next;
    }



// 翻轉(zhuǎn)一個(gè)子鏈表，并且用head迭代，當(dāng)head到尾部時(shí)缚俏，翻轉(zhuǎn)結(jié)束

class Solution {
public:
    // 翻轉(zhuǎn)一個(gè)子鏈表，并且返回新的頭與尾
    pair<ListNode*, ListNode*> myReverse(ListNode* head, ListNode* tail) {
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* nex = p->next;
            p->next = prev;
            prev = p;
            p = nex;
        }
        return {tail, head};
    }
     head
// 0->1->2->3->4->5
  hair  tail 
  pre
// 找到第一個(gè)翻轉(zhuǎn)的tail節(jié)點(diǎn)菱父，翻轉(zhuǎn)head力崇，tail節(jié)點(diǎn)，得到

    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分長(zhǎng)度是否大于等于 k古瓤，找到頭尾鏈表止剖，然后翻轉(zhuǎn)
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            // 這里是 C++17 的寫(xiě)法，也可以寫(xiě)成
            // pair<ListNode*, ListNode*> result = myReverse(head, tail);
            // head = result.first;
            // tail = result.second;
            tie(head, tail) = myReverse(head, tail);
            // 把子鏈表重新接回原鏈表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
};

5. 兩兩反轉(zhuǎn)鏈

// 迭代
ListNode* swapPairs(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    ListNode* p = head;
    ListNode* pre = dummy;
    while (p != NULL && p->next != NULL) {
        ListNode* cur = p->next;
        ListNode* next = cur->next;
        cur->next = p;
        pre->next = cur;
        pre = p;
        p->next = next;
        p = next;
    }
    return dummy->next;
}



// 遞歸
public ListNode swapPairs(ListNode head) {
    if (head == null || head.next == null) {
        return head;
    }
    ListNode nextHead = swapPairs(head.next.next);
    ListNode next = head.next;
    next.next = head;
    head.next = nextHead;
    return next;
}

6.旋轉(zhuǎn)鏈表
給你一個(gè)鏈表的頭節(jié)點(diǎn) head 落君，旋轉(zhuǎn)鏈表穿香，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置。
輸入：head = [1,2,3,4,5], k = 2
輸出：[4,5,1,2,3]

ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        ListNode* p = head;
        int size = 1;
        while (p->next != NULL) {
            p = p->next;
            size++;
        }
        k = k%size;
        if (k == 0) return head;
        while (k > 0 && fast->next != NULL) {
            fast = fast->next;
            k--;
        }
        while (fast->next != NULL) {
            fast = fast->next;
            slow = slow->next;
        }
        ListNode* newhead = slow->next;
        fast->next = head;
        slow->next = NULL;
        return newhead;
    }

7.分隔鏈表
給你一個(gè)鏈表的頭節(jié)點(diǎn) head 和一個(gè)特定值 x 绎速，請(qǐng)你對(duì)鏈表進(jìn)行分隔皮获，使得所有 小于 x 的節(jié)點(diǎn)都出現(xiàn)在 大于或等于 x 的節(jié)點(diǎn)之前。你應(yīng)當(dāng) 保留 兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置纹冤。
輸入：head = [1,4,3,2,5,2], x = 3
輸出：[1,2,2,4,3,5]

    ListNode *partition(ListNode *head, int x) {
        ListNode *dummy = new ListNode(-1);
        dummy->next = head;
        ListNode *pre = dummy, *cur = head;
        // 找到值大于x的停止
        while (pre->next && pre->next->val < x) pre = pre->next;
        cur = pre;
        // 
        while (cur->next) {
            if (cur->next->val < x) {
                ListNode *tmp = cur->next;
                cur->next = tmp->next;
                tmp->next = pre->next;
                pre->next = tmp;
                pre = pre->next;
            } else {
                cur = cur->next;
            }
        }
        return dummy->next;
    }

8.復(fù)制帶隨機(jī)指針的鏈表
時(shí)間復(fù)雜度：O(n)洒宝，其中 n 是鏈表的長(zhǎng)度。我們只需要遍歷該鏈表三次萌京。
空間復(fù)雜度：O(1)雁歌。注意返回值不計(jì)入空間復(fù)雜度。
第一種方法：
建立哈希表知残，然后遍歷鏈表靠瞎，深復(fù)制的同時(shí)將復(fù)制的舊節(jié)點(diǎn)作為key，新節(jié)點(diǎn)作為value存進(jìn)哈希表求妹，
第二次遍歷 以原鏈表的一個(gè)節(jié)點(diǎn)的隨機(jī)指針值作為索引乏盐，查找對(duì)應(yīng)的新鏈表的對(duì)應(yīng)節(jié)點(diǎn)的隨機(jī)指針值
第二種方法：將新老鏈表相互間隔的串為一個(gè)鏈表；然后制恍，處理random指針域父能；最后，將老新鏈表拆開(kāi)净神，并返回對(duì)應(yīng)的鏈表頭結(jié)點(diǎn)何吝。

    Node* copyRandomList(Node* head) {
        if (head == nullptr) {
            return nullptr;
        }
        // 1溉委、將新老結(jié)點(diǎn)串為一個(gè)鏈表
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = new Node(node->val);
            nodeNew->next = node->next;
            node->next = nodeNew;
        }
        //2、處理random指針域
        for (Node* node = head; node != nullptr; node = node->next->next) {
            Node* nodeNew = node->next;
            nodeNew->random = (node->random != nullptr) ? node->random->next : nullptr;
        }
        //3岔霸、將老新鏈表拆開(kāi)薛躬，返回新鏈表
        Node* headNew = head->next;
        for (Node* node = head; node != nullptr; node = node->next) {
            Node* nodeNew = node->next;
            node->next = node->next->next;
            nodeNew->next = (nodeNew->next != nullptr) ? nodeNew->next->next : nullptr;
        }
        return headNew;
    }

9.刪除鏈表重復(fù)元素

******************第一種，重復(fù)一個(gè)不留*****************
輸入：head = [1,2,3,3,4,4,5] 
輸出：[1,2,5]

ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL) return NULL;
        ListNode* pre = new ListNode();
        pre->next = head;
        ListNode* newhead = pre;
        ListNode* cur = head;
        while (cur->next!= NULL) {
            if(cur->val == cur->next->val) {
                while (cur->next != NULL && cur->val == cur->next->val)
                    cur = cur->next;
                if (cur->next == NULL) {
                    pre->next = NULL;
                    break;
                }
                pre->next = cur->next;
                cur = cur->next;
            } else {
                cur = cur->next;
                pre = pre->next;
            }
        }
    return newhead->next;
    }
    
********************第二種呆细，重復(fù)留一個(gè)******************
輸入：head = [1,2,3,3,4,4,5] 
輸出：[1,2,3,4,5]

    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL) return head;
        ListNode* pre = new ListNode();
        pre->next = head;
        ListNode* cur = head;
        ListNode* point = pre;
        while (cur->next != NULL) {
            while (cur->next != NULL && cur->next->val == cur->val) cur = cur->next;
            pre->next = cur;
            if (cur->next == NULL) {
                break;
            }
            cur = cur->next;
            pre = pre->next;
        }
        return point->next;
    }

10.合并k個(gè)鏈表：遞歸

image.png

  
# 最簡(jiǎn)單的方法
ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size()==0) return NULL;
        for(int i = 1; i < lists.size(); i++) {
            lists[i] = mergeTwoLists(lists[i-1],lists[i]);
        }
        return lists[lists.size()-1];
    }

    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == NULL && l2 == NULL) return NULL;
        if (l1 == NULL) return l2;
        if (l2 == NULL) return l1;
        ListNode* merged;
        if (l1->val > l2->val) {
            merged = l2;
            l2 = l2->next;
            merged->next= mergeTwoLists(l1,l2);
        } else {
            merged = l1;
            l1 = l1->next;
            merged->next = mergeTwoLists(l1,l2);
        }
        return merged;
    }


#  分治合并型宝，每次把list分成2個(gè)
class Solution {
        public ListNode mergeKLists(ListNode[] lists) {
            return merger(lists, 0, lists.length - 1);
        }

        private ListNode merger(ListNode[] lists, int l, int r) {
            if (l == r) {
                return lists[l];
            }
            if (l > r) {
                return null;
            }
            //右移一位相當(dāng)于除2
            int mid=(l+r)>>1;

            return mergeTwoLists(merger(lists,l,mid),merger(lists,mid+1,r));
        }


        public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
            ListNode pre = new ListNode(0);
            ListNode curr = pre;
            while (l1 != null || l2 != null) {
                if (l1 == null) {
                    curr.next = l2;
                    return pre.next;
                }

                if (l2 == null) {
                    curr.next = l1;
                    return pre.next;
                }

                if (l1.val < l2.val) {
                    curr.next = l1;
                    curr = curr.next;
                    l1 = l1.next;
                } else {
                    curr.next = l2;
                    curr = curr.next;
                    l2 = l2.next;
                }
            }

            return pre.next;
        }
    }