LeetCode-鏈表

鏈表（Linked List）是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針（Pointer）。

image-20191105225333488

由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到 O(1)O(1) 的復(fù)雜度，比另一種線性表 —— 順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問(wèn)特定編號(hào)的節(jié)點(diǎn)則需要 O(n)O(n) 的時(shí)間，而順序表相應(yīng)的時(shí)間復(fù)雜度分別是 O(log\ n)O(log n) 和 O(1)O(1)。

對(duì)于鏈表相關(guān)的問(wèn)題，應(yīng)該注意以下幾點(diǎn)：

頭節(jié)點(diǎn)的使用，即dummyNode的使用，可以減少邊界條件判斷。涉及到頭節(jié)點(diǎn)的操作，比如可能刪除head等等，使用dummyNode可以減少判斷。最后返回dummyNode.next
創(chuàng)建新的節(jié)點(diǎn)時(shí)，注意在棧上分配對(duì)象，如果使用new 需要delete。ps：后續(xù)一些題解沒(méi)有及時(shí)更正該方面的問(wèn)題。
快慢指針。多用于尋找中間節(jié)點(diǎn)等，衍生問(wèn)題環(huán)形鏈表等。主要在于在O(N)的時(shí)間來(lái)快速獲取到想要的節(jié)點(diǎn)。

使用快慢指針查找中間節(jié)點(diǎn)時(shí)，當(dāng)fast和slow都指向head和slow指向head，fast指向head->next 獲取到的中間節(jié)點(diǎn)及邊界條件不一致，需要注意。
cut函數(shù)，cut(ListNode* node,int k) 將鏈表前k個(gè)值切割，返回第k+1個(gè)node；多用于分隔鏈表。
反轉(zhuǎn)鏈表，需要pre=null,cur=head,next 三個(gè)指針，每次進(jìn)行更新，最后返回pre。
合并鏈表，注意dummyNode的使用以及邊界判空。
刪除節(jié)點(diǎn)，刪除當(dāng)前節(jié)點(diǎn)，可以將下個(gè)節(jié)點(diǎn)的值復(fù)制給當(dāng)前節(jié)點(diǎn)，并指向下下個(gè)節(jié)點(diǎn)。另一種思路時(shí)需要找到刪除節(jié)點(diǎn)的前驅(qū)。
時(shí)間復(fù)雜度，可以考慮一些輔助工作，如map，stack，set等。
另一個(gè)就是鏈表和排序算法以及樹(shù)的遍歷的結(jié)合。歸并排序，dfs等等?？梢缘群罄m(xù)章節(jié)進(jìn)行分析。
鏈表相關(guān)的問(wèn)題也可以考慮遞歸的方式進(jìn)行解決。從而簡(jiǎn)化問(wèn)題。

下面介紹LeetCode常見(jiàn)的鏈表問(wèn)題。

1.反轉(zhuǎn)鏈表

206.反轉(zhuǎn)鏈表。

示例:

輸入: 1->2->3->4->5->NULL
輸出: 5->4->3->2->1->NULL

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head==NULL || head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(cur){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

92.反轉(zhuǎn)鏈表II

反轉(zhuǎn)從位置 m 到 n 的鏈表。請(qǐng)使用一趟掃描完成反轉(zhuǎn)。

class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (head==NULL || head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(m>1){
            pre=cur;
            cur=cur->next;
            m--;
            n--;
        }
        // 需要記錄下pre 和 tail；即反轉(zhuǎn)后的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)
        ListNode* con = pre; //反轉(zhuǎn)后的頭節(jié)點(diǎn)
        ListNode* tail=cur; // 反轉(zhuǎn)后的尾節(jié)點(diǎn)
        while(n>0){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
            n--;
        }
        if(con){
            con->next=pre; //進(jìn)行連接            
        }else{
            head=pre; //此時(shí)證明從第一個(gè)節(jié)點(diǎn)開(kāi)始反轉(zhuǎn)，那么頭節(jié)點(diǎn)直接就是反轉(zhuǎn)后的頭節(jié)點(diǎn)
        }
        tail->next=cur; //尾節(jié)點(diǎn)的next設(shè)置為下一個(gè)節(jié)點(diǎn)cur
        return head;
    }
};

2.刪除元素

237.刪除鏈表中的節(jié)點(diǎn)

class Solution {
public:
    void deleteNode(ListNode* node) {
        //struct ListNode* tmp=node->next;
        node->val=node->next->val;
        node->next=node->next->next;
        //delete tmp;
    }
};

203.移除鏈表元素

刪除鏈表中等于給定值 *val* 的所有節(jié)點(diǎn)。

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        if(head==NULL){
            return NULL;
        }
        struct ListNode* t=new ListNode(-1);
        t->next=head;
        
        struct ListNode* pre=t;
        while(pre->next!=NULL){
            if (pre->next->val==val){
                auto s=pre->next;
                pre->next=pre->next->next;   
                delete s;
            }else{
                pre=pre->next;
            }
        }
        return t->next;
    }
};

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

給定一個(gè)鏈表，刪除鏈表的倒數(shù)第 n 個(gè)節(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(head==NULL || head->next==NULL){
            return NULL;
        }
        ListNode* first=head;
        ListNode* second=head;
        int i=0;
        // 先走n步，找到需要?jiǎng)h除的pre節(jié)點(diǎn)。
        while(i<n){ 
            first=first->next;
            i++;
        }
        //主要為了判斷是否是刪除首元素
        if(!first){
            return head -> next;    
        }
        while(first->next!=NULL){
            first=first->next;
            second=second->next;
        }
        ListNode* tmp=second->next;
        second->next=second->next->next;
        delete tmp;
        return head;
    }
};

83.刪除排序鏈表中的重復(fù)元素

給定一個(gè)排序鏈表，刪除所有重復(fù)的元素，使得每個(gè)元素只出現(xiàn)一次。

示例 1:

輸入: 1->1->2
輸出: 1->2

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur=head;
        while(cur!=NULL &&cur->next!=NULL){
            if(cur->next->val==cur->val){
                cur->next=cur->next->next;
            }else{
                cur=cur->next;
            }
        }
        return head;
        
    }
};

82.刪除排序鏈表中的重復(fù)元素II

給定一個(gè)排序鏈表，刪除所有含有重復(fù)數(shù)字的節(jié)點(diǎn)，只保留原始鏈表中 沒(méi)有重復(fù)出現(xiàn) 的數(shù)字。

提示：需要兩個(gè)指針；一個(gè)用來(lái)遍歷，另一個(gè)用來(lái)刪除。

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) return head;
        ListNode dummyNode(-1);
        ListNode* pre=&dummyNode;
        ListNode* cur=head;
        ListNode* tmp;
        int n,val;
        while(cur){
            tmp = cur;
            for(n=0,val=cur->val;cur!=NULL && cur->val==val;++n){
                cur=cur->next;
            }
            if (n==1){
                pre->next=tmp;
                pre=pre->next;
            }
        }
        pre->next=NULL;
        return dummyNode.next;
        
    }
};

1171.從鏈表中刪去總和值為0的連續(xù)節(jié)點(diǎn)

給你一個(gè)鏈表的頭節(jié)點(diǎn) head，請(qǐng)你編寫代碼，反復(fù)刪去鏈表中由總和值為 0 的連續(xù)節(jié)點(diǎn)組成的序列，直到不存在這樣的序列為止。刪除完畢后，請(qǐng)你返回最終結(jié)果鏈表的頭節(jié)點(diǎn)。

你可以返回任何滿足題目要求的答案。（注意，下面示例中的所有序列，都是對(duì) ListNode 對(duì)象序列化的表示。）

提示：我們可以考慮如果給的入?yún)⒉皇擎湵硎菙?shù)組的話，只需要求出前綴和，對(duì)于前綴和相同的項(xiàng)，那他們中間的部分即是可以消除掉的，比如以 [1, 2, 3, -3, 4] 為例，其前綴和數(shù)組為 [1, 3, 6, 3, 7] ，我們發(fā)現(xiàn)有兩項(xiàng)均為 3，則 6 和第二個(gè) 3 所對(duì)應(yīng)的原數(shù)組中的數(shù)字是可以消掉的。換成鏈表其實(shí)也是一樣的思路，把第一個(gè) 3 的 next 指向第二個(gè) 3 的 next 即可。

示例 1：

輸入：head = [1,2,-3,3,1]
輸出：[3,1]
提示：答案 [1,2,1] 也是正確的。

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        // 求和，當(dāng)出現(xiàn)重復(fù)是 證明兩個(gè)重復(fù)節(jié)點(diǎn)之間的數(shù)據(jù)可以被刪除；
        // 然后繼續(xù)遞歸； 返回值為dummy->next；
        if (head==NULL){
            return head;
        }
        ListNode dummy(0);
        dummy.next=head;
        ListNode* dummyPtr=&dummy;
        map<int,ListNode*> map;
        map[0]=dummyPtr;
        int sum=0;
        while(head!=NULL){
            sum+=head->val;
            if(map.find(sum)!=map.end()){
                map[sum]->next=head->next;
                return removeZeroSumSublists(dummy.next);
            }else{
                map[sum]=head;
                head=head->next;
            }
        }
        return dummy.next;   
    }
};

3.合并鏈表

合并鏈表，需要注意頭節(jié)點(diǎn)dummyNode的使用。另外為了降低復(fù)雜度，可以考慮使用歸并算法。

21.合并兩個(gè)有序鏈表

將兩個(gè)有序鏈表合并為一個(gè)新的有序鏈表并返回。新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

輸入：1->2->4, 1->3->4
輸出：1->1->2->3->4->4

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode dummy = ListNode(-1);  //  創(chuàng)建?？臻g對(duì)象即可。
        ListNode* prev = &dummy;   // 注意這里需要取地址&
        while(l1 != NULL && l2 != NULL) {
            if(l1->val <= l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1 != NULL ? l1 : l2;
        return dummy.next;
    }
};

23.合并K個(gè)有序鏈表

題解：已經(jīng)實(shí)現(xiàn)了合并兩個(gè)有序鏈表了，那么其實(shí)可以使用歸并的思想進(jìn)行合并k個(gè)鏈表，兩兩合并，時(shí)間復(fù)雜度為Nlogk

ListNode* mergeKLists(vector<ListNode*>& lists) {
        int len = lists.size();
        if(len < 1) return NULL;
        while(len>1){
            int m = (len + 1) / 2;
            for(int i=0;i<m && i+m < len;++i){
                lists[i] = mergeTwoLists(lists[i],lists[i+m]);
            }
            len = m;
        }
        return lists[0];
    }

2. 兩數(shù)相加

給出兩個(gè) 非空的鏈表用來(lái)表示兩個(gè)非負(fù)的整數(shù)。其中，它們各自的位數(shù)是按照逆序的方式存儲(chǔ)的，并且它們的每個(gè)節(jié)點(diǎn)只能存儲(chǔ) 一位數(shù)字。

如果，我們將這兩個(gè)數(shù)相加起來(lái)，則會(huì)返回一個(gè)新的鏈表來(lái)表示它們的和。

您可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)都不會(huì)以 0 開(kāi)頭。

示例：

輸入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出：7 -> 0 -> 8
原因：342 + 465 = 807

題解：新的節(jié)點(diǎn)等與兩個(gè)節(jié)點(diǎn)的(val+進(jìn)位)%10; 下一輪的進(jìn)位為(val+進(jìn)位)/10；

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *root=new ListNode(0);
        ListNode *cur=root;
        ListNode *tmp;
        int c=0;
        while(l1!=NULL || l2!=NULL || c!=0){ //注意邊界條件，可能最后只有進(jìn)位，需要?jiǎng)?chuàng)建新的節(jié)點(diǎn)
            int v1=l1?l1->val:0;
            int v2=l2?l2->val:0;
            int sum=v1+v2+c;
            c=sum/10;
            tmp=new ListNode(sum%10);
            cur->next=tmp;
            cur=tmp;
            if (l1){
                l1=l1->next; // 注意邊界條件
            }
            if (l2){
                l2=l2->next;
            }
        }
        return root->next;
    }
};

445.兩數(shù)相加II

給定兩個(gè)非空鏈表來(lái)代表兩個(gè)非負(fù)整數(shù)。數(shù)字最高位位于鏈表開(kāi)始位置。它們的每個(gè)節(jié)點(diǎn)只存儲(chǔ)單個(gè)數(shù)字。將這兩數(shù)相加會(huì)返回一個(gè)新的鏈表。你可以假設(shè)除了數(shù)字 0 之外，這兩個(gè)數(shù)字都不會(huì)以零開(kāi)頭。

進(jìn)階:如果輸入鏈表不能修改該如何處理？換句話說(shuō)，你不能對(duì)列表中的節(jié)點(diǎn)進(jìn)行翻轉(zhuǎn)。

示例:

輸入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
輸出: 7 -> 8 -> 0 -> 7

題解：當(dāng)當(dāng)前值的計(jì)算依賴下一項(xiàng)的計(jì)算時(shí)，可以使用遞歸的方法來(lái)實(shí)現(xiàn)回溯。當(dāng)前值=（val+下一項(xiàng)的進(jìn)位）/10。需要兩個(gè)鏈表等長(zhǎng)。另一種辦法是借助額外的結(jié)構(gòu)，來(lái)實(shí)現(xiàn)。例如棧/數(shù)組等。

class Solution {
public:
   ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        vector<ListNode*> l1v,l2v;
        to_vector(l1,l1v);
        to_vector(l2,l2v);
        int i=l1v.size()-1, j=l2v.size()-1;
        int d = 0;
        ListNode *head = NULL;
        while(i >= 0 || j >= 0){
            if(i >= 0) d += l1v[i--]->val;
            if(j >= 0) d += l2v[j--]->val;
            ListNode* p = new ListNode(d%10);
            p->next = head;
            head = p;
            d /= 10;
        }
        if(d) {
            ListNode* p = new ListNode(d);
            p->next = head;
            head = p;
        }
        return head;
    }
    
    void to_vector(ListNode* a,vector<ListNode*>& v){
        while(a){
            v.push_back(a);
            a = a->next;
        }
    }
};

4.重排鏈表

鏈表按照指定的規(guī)則進(jìn)行重新排序。比如首尾相連，交換鏈表節(jié)點(diǎn)等等。

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

給定一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后的鏈表。

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

示例:

給定 1->2->3->4, 你應(yīng)該返回 2->1->4->3.

題解：聲明dummyNode，pre指向dummy。 start指向1，end指向2. 讓pre.next=end;start.next=end.next;end.next=start. pre此刻再向前移動(dòng)到start。

class Solution {
   public ListNode swapPairs(ListNode head) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode temp = pre;
        while(temp.next != null && temp.next.next != null) {
            ListNode start = temp.next;
            ListNode end = temp.next.next;
            temp.next = end;
            start.next = end.next;
            end.next = start;
            temp = start;
        }
        return pre.next;
    }
}

25. k個(gè)一組反轉(zhuǎn)鏈表

給你一個(gè)鏈表，每 k 個(gè)節(jié)點(diǎn)一組進(jìn)行翻轉(zhuǎn)，請(qǐng)你返回翻轉(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

題解：合理利用cut函數(shù)，每k個(gè)一組，切割成鏈表，然后反轉(zhuǎn)，然后注意進(jìn)行鏈接。每次反轉(zhuǎn)前判斷下長(zhǎng)度是否達(dá)到k。當(dāng)對(duì)頭節(jié)點(diǎn)有進(jìn)行操作是，注意使用dummyNode。主要要保持鏈表直接的連接。

class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
         ListNode dummyHead(0);
         dummyHead.next=head;
         auto cur=dummyHead.next;
         auto tail = &dummyHead;
         while(cur){
            auto left = cur;
            cur = cut(left, k); // left->@->@ right->@->@->@...
            tail->next = reverseList(left,k);
            while(tail->next){
                tail=tail->next;
            }
        }
        return dummyHead.next;
    }
    
    // k個(gè)一組進(jìn)行反轉(zhuǎn)，采用cut函數(shù)，連接的時(shí)候，注意保證尾部正確。
    
    ListNode* cut(ListNode* head,int k){
        auto p=head;
        while(--k && p){
            p=p->next;
        }
        if(!p){
            return nullptr;
        }
        auto next=p->next;
        p->next=nullptr;
        return next;
    }
    
    ListNode* reverseList(ListNode* head,int k) {
        struct ListNode* p=head;
        while(p!=NULL){
            p=p->next;
            k--;
        }
        if (k>0){
            return head;
        }
        struct ListNode* pre=NULL;
        struct ListNode* cur=head;
        struct ListNode* tmp=NULL;
        while(cur){
            tmp=cur->next;
            cur->next=pre;
            pre=cur;
            cur=tmp;
        }
        return pre;
    }
};

61.旋轉(zhuǎn)鏈表

給定一個(gè)鏈表，旋轉(zhuǎn)鏈表，將鏈表每個(gè)節(jié)點(diǎn)向右移動(dòng) k 個(gè)位置，其中 k 是非負(fù)數(shù)。

輸入: 1->2->3->4->5->NULL, k = 2
輸出: 4->5->1->2->3->NULL
解釋:
向右旋轉(zhuǎn) 1 步: 5->1->2->3->4->NULL
向右旋轉(zhuǎn) 2 步: 4->5->1->2->3->NULL

題解：方法一：先連接，再旋轉(zhuǎn)。再斷開(kāi)。方法二：可以先整體逆序，然后前k個(gè)逆序，后n-k個(gè)逆序。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(head==NULL){
            return NULL;
        }
        if (head->next==NULL){
            return head;
        }
        ListNode *cur=head;
        int n=1;
        while(cur->next!=NULL){
            cur=cur->next;
            n++;
        }
        cur->next=head;
        ListNode *new_tail = head;
        int i=0;
        for(i=0;i<n - k % n - 1;++i){
            new_tail=new_tail->next;
        }
        ListNode* tmp=new_tail->next;
        new_tail->next=NULL;
        return tmp;
    }
};

143.重排鏈表

給定一個(gè)單鏈表 L：L0→L1→…→Ln-1→Ln ，
將其重新排列后變?yōu)椋?L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是單純的改變節(jié)點(diǎn)內(nèi)部的值，而是需要實(shí)際的進(jìn)行節(jié)點(diǎn)交換。

給定鏈表 1->2->3->4, 重新排列為 1->4->2->3.
給定鏈表 1->2->3->4->5, 重新排列為 1->5->2->4->3.

經(jīng)典問(wèn)題：考察快慢指針找中間節(jié)點(diǎn)；分隔鏈表；鏈表反轉(zhuǎn)，鏈表合并。需要考慮將中間節(jié)點(diǎn)分配到第一個(gè)鏈表還是第二個(gè)鏈表?？紤]清楚邊界條件。

class Solution {
public:
    void reorderList(ListNode* head) {
        // 先快慢指針找到中間節(jié)點(diǎn)，然后對(duì)后面的反轉(zhuǎn)，最后合并
        if(head==NULL || head->next==NULL){
            return ;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=NULL && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* l2=slow->next;
        slow->next=NULL;
        ListNode* l1=head;
        // 反轉(zhuǎn)list2
        ListNode* pre=NULL;
        ListNode* cur=l2;
        ListNode* next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        l2=pre;
        // 合并l1 l2
        while(l2!=NULL){
            slow=l1->next;
            fast=l2->next;
            l1->next=l2;
            l2->next=slow;
            l1=slow;
            l2=fast;
        }
        return;
    }
};

147.鏈表進(jìn)行插入排序

class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode h(-1);
        h.next = head;
        ListNode* pre = &h;
        ListNode* cur = head;
        ListNode* lat;
        ListNode* tmp;
        while (cur != NULL) {
            lat = cur->next; // 記錄下一個(gè)要插入排序的值
            if (lat != NULL && lat->val < cur->val) { 
                // 只有 cur.next 比 cur 小才需要向前尋找插入點(diǎn)
                while (pre->next != NULL && pre->next->val < lat->val) { 
                    pre = pre->next; // 繼續(xù)向后移動(dòng)
                }
                // 找到要插入的位置，此時(shí) pre 節(jié)點(diǎn)后面的位置就是 lat 要插入的位置
                tmp = pre->next;
                pre->next = lat;
                cur->next = lat->next;// 保證cur不斷
                lat->next = tmp;
                pre = &h;// 由于每次都是從前往后找插入位置，所以需要每次插入完成后要讓 pre 復(fù)位
            } else {
                // 都這直接把 cur 指針指向到下一個(gè)
                cur = lat;
            }
        }
       return h.next;
    }
};

148.排序鏈表

在 O(n log n) 時(shí)間復(fù)雜度和常數(shù)級(jí)空間復(fù)雜度下，對(duì)鏈表進(jìn)行排序。

題解：要求時(shí)間復(fù)雜度，考慮到歸并排序。兩兩合并，需要logn次。每次進(jìn)行n個(gè)比較。需要注意的點(diǎn)；cut函數(shù)實(shí)現(xiàn)，合并鏈個(gè)有序鏈表；dummyNode使用；鏈表的連接；等等。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        ListNode dummyHead(0);
        dummyHead.next=head;
        auto p=head;
        int length=len(p);
        for (int size=1;size<length;size<<=1){
            auto cur=dummyHead.next;
            auto tail = &dummyHead;
            while(cur){
                 auto left = cur;
                 auto right = cut(left, size); // left->@->@ right->@->@->@...
                 cur = cut(right, size); // left->@->@ right->@->@  cur->@->..
                 tail->next = merge(left, right);
                while(tail->next){
                    tail=tail->next;
                }
            }
        }
        return dummyHead.next;
    }
    
    int len(ListNode *p){
        int length=0;
         while (p) {
            ++length;
            p = p->next;
        }
        return length;
    }
    
    ListNode* cut(ListNode* head,int n ){
        auto p=head;
        while(--n && p){
            p=p->next;
        }
        if(!p){
            return nullptr;
        }
        auto next=p->next;
        p->next=nullptr;
        return next;
    }
    ListNode* merge(ListNode* l1, ListNode* l2) {
        ListNode dummyHead(0);
        auto p = &dummyHead;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                p->next = l1;
                p = l1;
                l1 = l1->next;       
            } else {
                p->next = l2;
                p = l2;
                l2 = l2->next;
            }
        }
        p->next = l1 ? l1 : l2;
        return dummyHead.next;
    }
};

5.分隔鏈表

86.分隔鏈表

給定一個(gè)鏈表和一個(gè)特定值 x，對(duì)鏈表進(jìn)行分隔，使得所有小于 x 的節(jié)點(diǎn)都在大于或等于 x 的節(jié)點(diǎn)之前。

你應(yīng)當(dāng)保留兩個(gè)分區(qū)中每個(gè)節(jié)點(diǎn)的初始相對(duì)位置。

題解：分解成兩個(gè)鏈表，再連接。注意dummyNode的使用。

class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        if (head==NULL ||head->next==NULL){
            return head;
        }            
        ListNode l_head(-1);
        ListNode r_head(-1);
        ListNode* l=&l_head;
        ListNode* r=&r_head;
        auto l_tmp=l;
        auto r_tmp=r;
        while(head!=NULL){
            if(head->val<x){
                l->next=head;
                l=l->next;
            }else{
                r->next=head;
                r=r->next;
            }
            head=head->next;
        }
        l->next=r_tmp->next;
        r->next=NULL;
        return l_tmp->next;
    }
};

109.有序鏈表轉(zhuǎn)換二叉搜索樹(shù)

給定一個(gè)單鏈表，其中的元素按升序排序，將其轉(zhuǎn)換為高度平衡的二叉搜索樹(shù)。

本題中，一個(gè)高度平衡二叉樹(shù)是指一個(gè)二叉樹(shù)每個(gè)節(jié)點(diǎn) 的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò) 1。

示例:

給定的有序鏈表： [-10, -3, 0, 5, 9],

一個(gè)可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面這個(gè)高度平衡二叉搜索樹(shù)：

題解：二叉搜索樹(shù)的前序遍歷為有序數(shù)組。那么對(duì)于鏈表中間節(jié)點(diǎn)即為跟節(jié)點(diǎn)。采用遞歸進(jìn)行遍歷即可。

class Solution {
public:
    TreeNode* sortedListToBST(ListNode* head) {
        //核心思想，中心節(jié)點(diǎn)就是根節(jié)點(diǎn)，遞歸構(gòu)造左右子節(jié)點(diǎn)。
        if(head==NULL){
            return NULL;
        }
        ListNode* mid=getMidNode(head);
        TreeNode* node=new TreeNode(mid->val);
        if (head==mid){
            return node;
        }
        node->left=sortedListToBST(head);
        node->right=sortedListToBST(mid->next);
        return node;
    }
    // 查找中間節(jié)點(diǎn)并返回。并分割left鏈表最后指向NULL。
    ListNode* getMidNode(ListNode *head){
        ListNode* pre=NULL;
        ListNode* slow=head;
        ListNode* fast=head;
        while(fast!=NULL && fast->next!=NULL){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        if (pre!=NULL){
            pre->next=NULL;
        }
        return slow;
        
    }
   
};

725.分隔鏈表

給定一個(gè)頭結(jié)點(diǎn)為 root 的鏈表, 編寫一個(gè)函數(shù)以將鏈表分隔為 k 個(gè)連續(xù)的部分。

每部分的長(zhǎng)度應(yīng)該盡可能的相等: 任意兩部分的長(zhǎng)度差距不能超過(guò) 1，也就是說(shuō)可能有些部分為 null。

這k個(gè)部分應(yīng)該按照在鏈表中出現(xiàn)的順序進(jìn)行輸出，并且排在前面的部分的長(zhǎng)度應(yīng)該大于或等于后面的長(zhǎng)度。

返回一個(gè)符合上述規(guī)則的鏈表的列表。

舉例： 1->2->3->4, k = 5 // 5 結(jié)果 [ [1], [2], [3], [4], null ]

示例 1：

輸入: 
root = [1, 2, 3], k = 5
輸出: [[1],[2],[3],[],[]]
解釋:
輸入輸出各部分都應(yīng)該是鏈表，而不是數(shù)組。
例如, 輸入的結(jié)點(diǎn) root 的 val= 1, root.next.val = 2, \root.next.next.val = 3, 且 root.next.next.next = null。
第一個(gè)輸出 output[0] 是 output[0].val = 1, output[0].next = null。
最后一個(gè)元素 output[4] 為 null, 它代表了最后一個(gè)部分為空鏈表。
示例 2：

輸入: 
root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3
輸出: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
解釋:
輸入被分成了幾個(gè)連續(xù)的部分，并且每部分的長(zhǎng)度相差不超過(guò)1.前面部分的長(zhǎng)度大于等于后面部分的長(zhǎng)度。

class Solution {
public:
    vector<ListNode*> splitListToParts(ListNode* root, int k) {
        // 遍歷root的長(zhǎng)度，得到len。 
        // if len<=k ; 那么每個(gè)都是獨(dú)立節(jié)點(diǎn)，再增加k-len個(gè)空節(jié)點(diǎn)。
        // if len>k; 那么切分為 len/k 個(gè)片段；其中 前 len%k個(gè)片段，長(zhǎng)度為 len/k + 1;
        // 實(shí)現(xiàn)cut(ListNode* head,int k); 切割前k個(gè)節(jié)點(diǎn)，返回第k+1個(gè)節(jié)點(diǎn)后的鏈表
        // 循環(huán)切割，時(shí)間復(fù)雜度為O(N)
        vector<ListNode*> vec;
        ListNode* cur=root;
        int len=getLen(root);
        if (len<k){
            for(int i=0;i<k;i++){
                vec.push_back(cur);
                cur=cut(cur,1);
            }
        }else{
            int step=len/k;
            int m=len%k;
            int i=0;
            for (i=0;i<m;i++){
                vec.push_back(cur);
                cur=cut(cur,step+1);
            }
            for(i=m;i<k;i++){
                vec.push_back(cur);
                cur=cut(cur,step);
            }
        }
        return vec;
    }
    
    int getLen(ListNode* head){
        if(head==NULL){
            return 0;
        }
        int len=0;
        ListNode* cur=head;
        while(cur){
            cur=cur->next;
            len++;
        }
        return len;
    }
    
    ListNode* cut(ListNode* head,int k){
        while(k>1 && head){
            head=head->next;
            k--;
        }
        if (head==NULL){
            return NULL;
        }
        ListNode* tmp=head->next;
        head->next=NULL;
        return tmp;
    }
};

6.使用額外結(jié)構(gòu)降低時(shí)間復(fù)雜度

138.復(fù)制帶隨機(jī)指針的鏈表

給定一個(gè)鏈表，每個(gè)節(jié)點(diǎn)包含一個(gè)額外增加的隨機(jī)指針，該指針可以指向鏈表中的任何節(jié)點(diǎn)或空節(jié)點(diǎn)。

要求返回這個(gè)鏈表的深拷貝。

題解：先全部復(fù)制一遍，再進(jìn)行指針關(guān)聯(lián)

class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node() {}

    Node(int _val, Node* _next, Node* _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
public:
    // hash 空間復(fù)雜O(N) 
    // 原地復(fù)制 空間復(fù)雜O(1) 復(fù)制節(jié)點(diǎn) 復(fù)制random 拆鏈表
    Node* copyRandomList(Node* head) {
        if(head==nullptr){
            return nullptr;
        }
        map<Node*,Node*> map;
        Node* cur=head;
        while(cur){
            map[cur]=new Node(cur->val,nullptr,nullptr);
            cur=cur->next;
        }
        cur=head;
        while(cur){
            map[cur]->next=map[cur->next];
            map[cur]->random=map[cur->random];
            cur=cur->next;
        }
        return map[head];
    }
};

817.鏈表組件

給定一個(gè)鏈表（鏈表結(jié)點(diǎn)包含一個(gè)整型值）的頭結(jié)點(diǎn) head。

同時(shí)給定列表 G，該列表是上述鏈表中整型值的一個(gè)子集。

返回列表 G 中組件的個(gè)數(shù)，這里對(duì)組件的定義為：鏈表中一段最長(zhǎng)連續(xù)結(jié)點(diǎn)的值（該值必須在列表 G 中）構(gòu)成的集合。

示例 1：

輸入: 
head: 0->1->2->3
G = [0, 1, 3]
輸出: 2
解釋: 
鏈表中,0 和 1 是相連接的，且 G 中不包含 2，所以 [0, 1] 是 G 的一個(gè)組件，同理 [3] 也是一個(gè)組件，故返回 2。
示例 2：

輸入: 
head: 0->1->2->3->4
G = [0, 3, 1, 4]
輸出: 2
解釋: 
鏈表中，0 和 1 是相連接的，3 和 4 是相連接的，所以 [0, 1] 和 [3, 4] 是兩個(gè)組件，故返回 2。

class Solution {
public:
    int numComponents(ListNode* head, vector<int>& G) {
        set<int> m_set;
        for (int i=0;i<G.size();i++){
            m_set.insert(G[i]);
        }
        ListNode* cur=head;
        int num = 0;
        while(cur){
            if(m_set.find(cur->val)!= m_set.end() && (cur->next==NULL || m_set.find(cur->next->val)== m_set.end())){
                num++;
            }
            cur=cur->next;
        }
        return num;
        
    }
};

1019.鏈表中下一個(gè)更大節(jié)點(diǎn)

給出一個(gè)以頭節(jié)點(diǎn) head 作為第一個(gè)節(jié)點(diǎn)的鏈表。鏈表中的節(jié)點(diǎn)分別編號(hào)為：node_1, node_2, node_3, ... 。

每個(gè)節(jié)點(diǎn)都可能有下一個(gè)更大值（next larger value）：對(duì)于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的選項(xiàng)中最小的那個(gè)。如果不存在這樣的 j，那么下一個(gè)更大值為 0 。

返回整數(shù)答案數(shù)組 answer，其中 answer[i] = next_larger(node_{i+1}) 。

注意：在下面的示例中，諸如 [2,1,5] 這樣的輸入（不是輸出）是鏈表的序列化表示，其頭節(jié)點(diǎn)的值為 2，第二個(gè)節(jié)點(diǎn)值為 1，第三個(gè)節(jié)點(diǎn)值為 5 。

示例 1：

輸入：[2,1,5]
輸出：[5,5,0]
示例 2：

輸入：[2,7,4,3,5]
輸出：[7,0,5,5,0]
示例 3：

輸入：[1,7,5,1,9,2,5,1]
輸出：[7,9,9,9,0,5,0,0]

class Solution {
public:
   //題解，使用棧先進(jìn)后出。找到第一個(gè)比較大的就更新對(duì)應(yīng)的數(shù)組值。
    vector<int> nextLargerNodes(ListNode* head) {
        int count = 0; //計(jì)數(shù)，作為下標(biāo)
        vector<int> result;
        stack<pair<int, int>> tmp; //first為val，second為下標(biāo)
        while (head)
        {
            result.push_back(0); //給result數(shù)組后面+0，1為保證長(zhǎng)度，2是默認(rèn)值（后無(wú)更大的值的話）為0
            while (!tmp.empty() &&
                   head->val > tmp.top().first) //棧不為空且head指針的val值大于棧頂?shù)脑氐闹?            {
                result[tmp.top().second] = head->val; //result數(shù)組修改，滿足題意要求的最大值，然后出棧，繼續(xù)循環(huán)
                tmp.pop();
            }
            tmp.push(make_pair(head->val, count++)); //count++計(jì)數(shù)
            head = head->next; //下一個(gè)節(jié)點(diǎn)
        }
        return result;       
    }
};

7.快慢指針

160.相交鏈表

編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int aLen=0;
        int bLen=0;
        ListNode *curA=headA;
        ListNode *curB=headB;
        while(curA!=NULL){
            curA=curA->next;
            aLen++;
        }
        while(curB!=NULL){
            curB=curB->next;
            bLen++;
        }
        int i=0;
        curA=headA;
        curB=headB;
        if (aLen>bLen){
            for(i=0;i<aLen-bLen;i++){
                curA=curA->next;
            }
        }else{
            for(i=0;i<bLen-aLen;i++){
                curB=curB->next;
            }   
        }
        while(curA){
            if(curA==curB){
                return curA;
            }else{
                curA=curA->next;
                curB=curB->next;
                i++;
            } 
        }
        return NULL;
    }
};

234.回文鏈表

請(qǐng)判斷一個(gè)鏈表是否為回文鏈表。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return true;
        }
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(fast!=NULL && fast->next!=NULL){
            fast=fast->next->next;
            slow=slow->next;
        }
        ListNode* r=resver(slow->next);
        while(r!=NULL){
            if(r->val!=head->val){
                return false;
            }
            r=r->next;
            head=head->next;
        }
        return true;
    }
    
    ListNode* resver(ListNode* head){
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* pre=NULL;
        ListNode* cur=head;
        ListNode* next;
        while(cur!=NULL){
            next=cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

328.奇偶鏈表

給定一個(gè)單鏈表，把所有的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)分別排在一起。請(qǐng)注意，這里的奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)指的是節(jié)點(diǎn)編號(hào)的奇偶性，而不是節(jié)點(diǎn)的值的奇偶性。

請(qǐng)嘗試使用原地算法完成。你的算法的空間復(fù)雜度應(yīng)為 O(1)，時(shí)間復(fù)雜度應(yīng)為 O(nodes)，nodes 為節(jié)點(diǎn)總數(shù)。

示例 1:

輸入: 1->2->3->4->5->NULL
輸出: 1->3->5->2->4->NULL
示例 2:

輸入: 2->1->3->5->6->4->7->NULL
輸出: 2->3->6->7->1->5->4->NULL
說(shuō)明:

應(yīng)當(dāng)保持奇數(shù)節(jié)點(diǎn)和偶數(shù)節(jié)點(diǎn)的相對(duì)順序。
鏈表的第一個(gè)節(jié)點(diǎn)視為奇數(shù)節(jié)點(diǎn)，第二個(gè)節(jié)點(diǎn)視為偶數(shù)節(jié)點(diǎn)，以此類推。

class Solution {
public:
    ListNode* oddEvenList(ListNode* head) {
        if(head==NULL||head->next==NULL){
            return head;
        }
        ListNode* t1=head;
        ListNode* t2=head->next;
        ListNode* t2head=t2; //必須先保存，才可以保證鏈接。因?yàn)楹罄m(xù)head->next 變了。
        while(t2!=NULL && t2->next!=NULL){
            t1->next=t2->next;
            t1=t1->next;
            t2->next=t1->next;
            t2=t2->next;
        }
        t1->next=t2head;
        return head;
    }
};

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

LeetCode-鏈表

LeetCode-鏈表

LeetCode-鏈表

1.反轉(zhuǎn)鏈表

206.反轉(zhuǎn)鏈表。

92.反轉(zhuǎn)鏈表II

2.刪除元素

237.刪除鏈表中的節(jié)點(diǎn)

203.移除鏈表元素

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

83.刪除排序鏈表中的重復(fù)元素

82.刪除排序鏈表中的重復(fù)元素II

1171.從鏈表中刪去總和值為0的連續(xù)節(jié)點(diǎn)

3.合并鏈表

21.合并兩個(gè)有序鏈表

23.合并K個(gè)有序鏈表

2. 兩數(shù)相加

445.兩數(shù)相加II

4.重排鏈表

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

25. k個(gè)一組反轉(zhuǎn)鏈表

61.旋轉(zhuǎn)鏈表

143.重排鏈表

147.鏈表進(jìn)行插入排序

148.排序鏈表

5.分隔鏈表

86.分隔鏈表

109.有序鏈表轉(zhuǎn)換二叉搜索樹(shù)

725.分隔鏈表

6.使用額外結(jié)構(gòu)降低時(shí)間復(fù)雜度

138.復(fù)制帶隨機(jī)指針的鏈表

817.鏈表組件

1019.鏈表中下一個(gè)更大節(jié)點(diǎn)

7.快慢指針

160.相交鏈表

234.回文鏈表

328.奇偶鏈表

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

LeetCode-鏈表

LeetCode-鏈表

1.反轉(zhuǎn)鏈表

206.反轉(zhuǎn)鏈表。

92.反轉(zhuǎn)鏈表II

2.刪除元素

237.刪除鏈表中的節(jié)點(diǎn)

203.移除鏈表元素

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

83.刪除排序鏈表中的重復(fù)元素

82.刪除排序鏈表中的重復(fù)元素II

1171.從鏈表中刪去總和值為0的連續(xù)節(jié)點(diǎn)

3.合并鏈表

21.合并兩個(gè)有序鏈表

23.合并K個(gè)有序鏈表

2. 兩數(shù)相加

445.兩數(shù)相加II

4.重排鏈表

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

25. k個(gè)一組反轉(zhuǎn)鏈表

61.旋轉(zhuǎn)鏈表

143.重排鏈表

147.鏈表進(jìn)行插入排序

148.排序鏈表

5.分隔鏈表

86.分隔鏈表

109.有序鏈表轉(zhuǎn)換二叉搜索樹(shù)

725.分隔鏈表

6.使用額外結(jié)構(gòu)降低時(shí)間復(fù)雜度

138.復(fù)制帶隨機(jī)指針的鏈表

817.鏈表組件

1019.鏈表中下一個(gè)更大節(jié)點(diǎn)

7.快慢指針

160.相交鏈表

234.回文鏈表

328.奇偶鏈表

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av