---

一、鏈表分割

鏈表分割

題目描述的意思就如下圖：

也就是把1，2挪到前面，6，3，5挪到后面，前者的相對順序不發生改變

這里要想往后挪就要先遍歷，遍歷到6比3小，這里要通過刪除6這個節點然后尾插到后面來實現嗎？這樣就太麻煩了

思路：創建兩個非空鏈表（小鏈表，大鏈表），遍歷原鏈表，小的尾插到小鏈表中，大的尾插到大鏈表中（簡單的將節點分為小于x的節點和大于等于x的節點），最終大鏈表和小鏈表首尾相連






注意：這里第一個參數是鏈表，所以我們就加一個大括號，然后節點之間用逗號分隔，兩個參數之間也要用逗號分隔

這串代碼看似沒有問題

然而提交出現了錯誤，出現內存超限的原因有兩種，第一種是陷入死循環，第二種是無限遞歸（無線創建函數棧幀），首先排除死循環，因為自測結果沒有出錯，那么就是節點出現問題了
這里改一下節點順序


發現出現死循環，1，2，5，3，6打印完之后又從2開始打印，6拿過來尾插之后，其的next指針沒有發生改變，還是指向2這個節點

解決方法很簡單，讓大鏈表的尾節點置為空就好

---

二、隨機鏈表的復制

隨機鏈表的復制

補充一下題目中所說的深/淺拷貝是什么意思
淺拷貝：就是值拷貝

如圖將pcur指向節點3進行淺拷貝，只需要讓新的指針指向3即可
如果是深拷貝就要向操作系統額外申請一個節點大小的空間

乍一看這個題很簡單

這里定義pcur來遍歷原鏈表，只要節點不為空，就復制該節點
首先向操作系統malloc一塊一摸一樣節點大小的空間

新的節點的值和原節點相等，next和random的值初始情況下置為空，接下來pcur往后走，只要節點不為空，就把13這個節點拿到復制鏈表進行尾插，新節點的13（next，random都默認為空），新節點7的next指針指向13

依次類推

但是尾插的時候只能設置當前節點里的值和next指針，這個random指針怎么做呢？
如果我再讓pcur回到第一個節點，發現原鏈表的random指針置為空，便讓新鏈表的random指針置為空

還需要定義一個指針遍歷新的鏈表，也就是操作完一個節點pcur和copy都要往后走，但是發現13的random指針指向前一個節點，單鏈表又是單向的，這里是頭節點

如果10的random節點指向13，這就不好找了，又要從頭向后遍歷

新的思路：（1）就是在原鏈表的基礎上拷貝節點

從頭開始遍歷，遍歷到7，創建一個和7一摸一樣的節點（malloc），然后讓newnode尾插到pcur節點之后，newndoe的next指針指向pcur的下一個節點，pcur的下一個節點用next保存

尾插之后pcur指向其原來指向的next節點，只要13這個節點不為空，再深拷貝一個13節點，然后把新的節點拿到13節點之后尾插，然后pcur->next指針指向newnode，newnode->next指針指向next節點，以此類推，循環往復

pcur跳出循環,不能對空節點進行深拷貝

（2）設置random指針

這里原鏈表中7的random指針置為空，那么復制節點的ramdom也置為空，然后copy往后走，cur也往后走（這里cur原來是在原節點7的位置）
原鏈表13的random指針是7，那么copy節點的random指針滿足下面的條件，當原鏈表里的random指針不為空，就滿足這樣一個規則

cur->random指針指向7，其的next節點就是復制節點的random指針指向的節點

此時copy和cur都往后走，以此類推，循環往復

此時只要cur的random指針不為空，就可以執行該規則


當cur為空，拷貝節點的random指針都設置完了

（3）斷開新舊鏈表

這里斷開可以讓拷貝節點指向其下一個節點，原鏈表的next指針其實不用管，雖然原鏈表的next指針指向新鏈表，但是并不影響新鏈表，新鏈表連到一起打印的時候，并不會打印到原鏈表里面

所以這里新舊鏈表的斷開可以讓新鏈表的next指針指向自己的節點，也可以讓原鏈表的next指針也指向自己的節點，改不改都不影響，這里我就不管了，只要新鏈表是獨立的鏈表就好了

這里拷貝鏈表的頭和尾初始情況下指向pcur的下一個節點，只要copyTail的下一個節點不為空，就意味著pcur的下一個節點非空，讓pcur走到復制節點尾節點的下一個節點，再讓復制節點7的next指針不再指向原節點13，而是指向pcur的下一個節點，此時pcur的下一個節點就是新節點13，此時13稱為拷貝鏈表的新的尾節點，這里要兩張圖結合來看

以此類推，循環往復

這里只要copyTail的下一個節點不為空，這里pcur可以走到copyTail的下一個節點，再讓copyTail->next指針指向pcur的下一個節點

然后1變為新的尾節點，這里copyTail的下一個節點為空了，此時就把舊鏈表從新鏈表里面斷開了。

直接返回拷貝后鏈表的頭節點就好了

/*** Definition for a Node.* struct Node {*     int val;*     struct Node *next;*     struct Node *random;* };*/typedef struct Node Node;//創建新節點Node* buyNode(int x){Node* newnode=(Node*)malloc(sizeof(Node));newnode->val=x;newnode->next=newnode->random=NULL;return newnode;}//在原鏈表的基礎上拷貝節點插入原鏈表中
void AddNode(Node* head)
{Node* pcur=head;while(pcur){Node* newnode=buyNode(pcur->val);Node* next=pcur->next;newnode->next=next;pcur->next=newnode;pcur=next;}
}//設置random
void setRandom(Node* head)
{Node* pcur=head;while(pcur){Node* copy=pcur->next;if(pcur->random){copy->random=pcur->random->next;}pcur=copy->next;}
}
struct Node* copyRandomList(struct Node* head) {if(head==NULL){return head;}//在原鏈表的基礎上拷貝節點并插入到原鏈表中AddNode(head);//設置randomsetRandom(head);//分開新舊鏈表Node* pcur=head;Node* copyHead,*copyTail;copyHead=copyTail=pcur->next;while(copyTail->next){pcur=copyTail->next;copyTail->next=pcur->next;copyTail=copyTail->next;}return copyHead;
}

---

總結

第二道題徹底把博主寫傻了，論寫到最后圖都背下來了的救贖感（