移除鏈表元素+反轉鏈表+鏈表的中間節點+合并兩個有序鏈表+環形鏈表約瑟夫問題+分割鏈表

一、移除鏈表元素

給你一個鏈表的頭節點 phead?和一個整數 val?，請你刪除鏈表中所有滿足 Node.val == val?的節點，并返回?新的頭節點?

(列表中的節點數目在范圍?[0, 104]?內)

示例：輸入：head = [1,2,6,3,4,5,6], val = 6? ? ? ? ??輸出：[1,2,3,4,5]

? ? ? ? ? 輸入：head = [ ], val = 1? ? ? ? ? ? ? ? ? ? ? ? ? ? ??輸出：[ ]?

? ? ? ? ? 輸入：head = [7,7,7,7], val = 7? ? ? ? ? ? ? ? ? ??輸出：[ ]

思路1：創建一個新鏈表，遍歷找值不為val的節點，尾插到新的鏈表中

需要創建一個指針pcur，讓它從phead開始尋找不為val的節點，將它們尾插在新的鏈表中，至于等于val的節點就跳過它；除此之外，我們還需要創建一個新鏈表，用兩個指針newHead,newTail來保存新的頭節點和尾節點，開始時先將它們置為NULL。

但是需要注意：根據題目給的鏈表內節點數目的范圍，可知鏈表有為空的情況，需要判空，如果原鏈表為空，意味著原鏈表內沒有任何節點，那么就不需要再進行遍歷循環，直接跳出了函數，返回一個空的新鏈表

//移除鏈表元素函數
SLNode* removeElements(SLNode* phead,int val)
{//創建新鏈表SLNode* newHead = NULL;SLNode* newTail = NULL;//遍歷原鏈表SLNode* pcur = phead;while(pcur){//找到不為val的節點，尾插到新鏈表中if(pcur->val != val){//鏈表為空if(newHead == NULL){newHead = newTail = pcur;}else{//鏈表不為空newTail->next = pcur;newTail = newTail->next;}}pcur = pcur->next;}if(newTail) //當原鏈表為空時，不需要進行置空操作newTail->next = NULL;//返回新的頭節點return newHead;
}
//創建單鏈表節點結構
typedef struct SListNode
{int val;struct SListNode* next;
}SLNode;
//創建新節點
SLNode* newnode(int x)
{SLNode* node = (SLNode*)malloc(sizeof(SLNode));if(node == NULL){perror("malloc");exit(1);}node->val = x;node->next = NULL;return node;
}
//打印鏈表
void Print(SLNode* phead)
{SLNode* pcur = phead;while(pcur){printf("%d ",pcur->val);pcur = pcur->next;}printf("\n");
}
int main()
{//創建測試鏈表：1->2->6->3->4->5->6SLNode* phead = newnode(1);phead->next = newnode(2);phead->next->next = newnode(6);phead->next->next->next = newnode(3);phead->next->next->next->next = newnode(4);phead->next->next->next->next->next = newnode(5);phead->next->next->next->next->next->next = newnode(6);printf("原始鏈表:");Print(phead);int val = 6;SLNode* result = removeElements(phead,val);printf("移除%d后的新鏈表:"，val);Print(result);//釋放鏈表內存while(result){SLNode* tmp = result;result = result->next;free(tmp);tmp = NULL;}return 0;
}

測試原鏈表為空時：

SLNode* phead = NULL;

測試原鏈表元素相同時：

SLNode* phead = newnode(7);
phead->next = newnode(7);
phead->next->next = newnode(7);
phead->next->next->next = newnode(7);int val = 7;

思路2：遍歷原鏈表，將值為val的節點釋放

使用 prev,pcur,next三指針法：pcur表示當前的節點，prev表示當前節點的前一個節點，next表示當前節點的下一個節點；將pcur節點釋放掉之前，需要改變prev的next節點變為next，才能將其釋放掉，初始時將prev和next置為NULL

SLNode* removeElements(SLNode* phead,int val)
{SLNode* prev = NULL;//前一個節點指針SLNode* pcur = phead;//當前節點指針SLNode* next = NULL;//下一個節點指針while(pcur){next = pcur->next;//保存下一個節點if(pcur->val == val){//刪除當前節點if(prev == NULL){//刪除的是頭節點phead = next;//更新頭指針}else{//刪除的是中間或尾節點prev->next = next;//釋放當前節點內存free(pcur);pcur = NULL;}}else{//當前節點保留，更新prev指針prev = pcur;}//移動到下一個節點pcur = next;}return phead;
}

二、反轉鏈表

給你單鏈表的頭節點 phead?，請你反轉鏈表，并返回反轉后的鏈表。

(鏈表中節點的數目范是?[0, 5000])

示例：?輸入：head = [1,2,3,4,5]? ? ??輸出：[5,4,3,2,1]

? ? ? ? ? ? 輸入：head = [1,2]? ? ? ? ? ? ? ?輸出：[2,1]

? ? ? ? ? ? 輸入：head = [ ]? ? ? ? ? ? ? ? ? ??輸出：[ ]

思路1：創建新鏈表，將原鏈表中的節點拿過來頭插

用兩個指針newHead,newTail來保存新鏈表的頭節點和尾節點，每頭插一個節點newHead就跟著變化，變成新的頭節點

根據題目節點的數目范圍可知，鏈表有可能為空鏈表，因此需要判空。

SLNode* reverseList(SLNode* phead)
{//創建一個空鏈表SLNode* newHead = NULL;SLNode* newnode = NULL;//遍歷原鏈表SLNode* pcur = phead;while(pcur){//1.保存下一個節點（防止丟失）SLNode* next = pcur->next;if(newHead == NULL){newHead = newTail = pcur;pcur->next = NULL;}else{//2.將當前節點插入新鏈表頭部pcur->next = newHead;//當前節點指向新鏈表的第一個節點newHead = pcur;//更新新鏈表頭指針}//3.移動到原鏈表的下一個節點pcur = next;}return newHead; //如果元鏈表為空，直接會返回NULL
}

如果新鏈表只給一個指針newHead來維護：

SLNode* reverseList(ListNode* phead)
{//創建新鏈表SLNode* newHead = NULL;//遍歷鏈表SLNode* pcur = phead;    while(pcur){//1.保存下一個節點（防止丟失）SLNode* next = pcur->next;//2.將當前節點插入新鏈表頭部pcur->next = newHead;newHead = pcur;//3.移動到原鏈表的下一個節點pcur = next;}return newHead;
}

思路2：創建三個指針，完成原鏈表的反轉

創建三個指針n1,n2,n3，分別表示當前節點的前一個節點，當前節點，當前節點的后一個節點，開始時n1置為NULL。具體做法：(1)讓n2的next指針指向n1

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? (2)然后n1=n2; n2=n3; n3=n3->next

SLNode* reverseList(ListNode* phead)
{//判空if(phead == NULL){return NULL;}//創建三個指針SLNode* n1,n2,n3;n1 = NULL,n2 = phead, n3 = n2->next;while(n2){n2->next = n1;n1 = n2;n2 = n3;if(n3)n3 = n3->next;}//指向新的頭節點n1return n1;
}

三、鏈表的中間節點

給你單鏈表的頭結點?phead?，請你找出并返回鏈表的中間結點。

如果有兩個中間結點，則返回第二個中間結點。

（鏈表的結點數范圍是?[1, 100]）

示例：輸入：head = [1,2,3,4,5]? ??輸出：[3,4,5] （鏈表只有一個中間結點，值為 3）

輸入：head = [1,2,3,4,5,6]??輸出：[4,5,6] （該鏈表有兩個中間結點，值分別為 3 和 4 ，返回第二個結點）

思路1：遍歷原鏈表，使用count變量計數，直接返回 count/2 節點

例如，當有奇數個節點時，5個節點，則 5/2=2，2即中間節點

? ? ? ? ? ?當有偶數個節點時，6個節點，則 6/2=3，3即中間節點

SLNode* middleNode(SLNode* phead)
{if(phead == NULL){return NULL; //空鏈表直接返回}//第一次遍歷：計算鏈表長度int count = 0;SLNode* pcur =phead;while(pcur){count++;pcur = pcur->next;}//計算中間位置int mid = count/2;//第二次遍歷：移動到中間節點pcur = phead;if(int i = 0;i < mid; i++){pcur = pcur->next;}return pcur;
}

測試奇數個節點時：

測試偶數個節點時：

測試只有一個節點和空鏈表時：

思路2：快慢指針

slow每次走一步，fast每次走兩步，

例如，當有奇數個節點時，5個節點，slow走一步，fast走兩步，到最后一個節點時，fast->next 剛好等于NULL(fast->next == NULL)，slow指向的剛好是中間節點；

當有偶數個節點時，6個節點，slow走一步，fast走兩步，到最后一個節點時，fast剛好等于NULL(fast == NULL),slow指向的剛好是中間節點

SLNode* middleNode(SLNode* phead)
{if(phead == NULL){return NULL;}//創建快慢指針SLNode* slow = phead;SLNode* fast = phead;//快指針每次移動兩步，慢指針每次移動一步while(fast && fast->next) //不可以反過來寫成 (fast->next && fast),因為如果鏈表中有偶數個節點的情況下，fast最后一次會直接走空 NULL，{                         //fast->next執行會報錯slow = slow->next;    fast = fast->next->next;}//此時slow剛好指向的就是中間節點return slow;
}

四、合并兩個有序鏈表

將兩個升序鏈表合并為一個新的?升序?鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

（兩個鏈表的節點數目范圍是?[0, 50]，

?l1?和?l2?均按?非遞減順序?排列）

示例：輸入：l1 = [1,2,4] , l2 = [1,3,4]? ? ? ?輸出：[1,1,2,3,4,4]

? ? ? ? ? ?輸入：l1 = [ ], l2 = [ ]? ? ? ? ? ? ? ? ? ? ??輸出：[ ]

? ? ? ? ? ?輸入：l1 = [ ] , l2 = [0]? ? ? ? ? ? ? ? ? ? ?輸出：[0]

思路：創建一個空鏈表，遍歷原鏈表，將節點值小的節點拿到新的鏈表中進行尾插操作

需要創建兩個指針l1,l2，分別遍歷兩個原鏈表，還要創建一個新的鏈表，同時維護新鏈表的頭指針(newHead)和尾指針(newTail)

和前面我們做的順序表的合并兩個有序數組算法題一樣，結果只有兩種情況：要么l1為空，要么l2為空

SLNode* mergeTwoLists(SLNode* list1,SLNode* list2)
{//判空if(list1 == NULL){return list2;//如果兩個鏈表都為空，則會返回空鏈表[ ]}if(list2){return list1;}SLNode* l1 = list1;SLNode* l1 = list2;//創建新鏈表SLNode* newHead,newTail;newHead = newTail = NULL;while(l1 && l2){if(l1->val < l2->val){//l1拿下來尾插if(newHead == NULL){newHead = newTail = l1;}else{newTail->next = l1;newTail = newTail->next;}l1 = l1->next;}else{//l2拿下來尾插if(newHead == NULL){newHead = newTail = l2;}else{newTail->next = l2;newTail = newTail->next;}l2 = l2->next;}}//跳出循環有兩種情況：要么l1走到空，要么l2走到空if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}return newHead;
}

測試空鏈表時：

測試有一個鏈表為空一個不為空時：

添加哨兵位節點優化代碼

在上面的代碼中，存在重復的代碼(如下圖所示)，如何優化？

重復的原因：新鏈表存在空鏈表和非空鏈表兩種情況，解決思路：讓新鏈表不為空--頭尾指針都指向一個有效的地址（節點），即使用帶頭鏈表（哨兵位節點）

將較小的節點一個個尾插到新鏈表的哨兵節點后面，遍歷完成之后返回的是鏈表的第一個有效節點

（哨兵節點詳情：數據結構-單鏈表-CSDN博客）

SLNode* mergeTwoLists(ListNode* list1, ListNode* list2)
{//判空if (list1 == NULL){return list2;// [ ]如果兩個鏈表都為空，則會返回空鏈表}if (list2 == NULL){return list1;}SLNode* l1 = list1;SLNode* l2 = list2;//創建新的鏈表SLNode* newHead,*newTail;//創建哨兵節點newHead = newTail = (SLNode*)malloc(sizeof(SLNode));while(l1 && l2){if(l1->val <l2->val){newTail->next = l1;newTail = newTail->next;l1 = l1->next;}else{newTail->next = l2;newTail = newTail->next;l2 = l2->next;}}if(l1){newTail->next = l1;}if(l2){newTail->next = l2;}//動態申請的空間手動釋放掉SLNode* ret = newHead->next; //返回的是第一個有效節點free(newHead);newHead = NULL;return ret;
}

五、循環鏈表經典應用-環形鏈表的約瑟夫問題

【背景：著名的Josephus問題

據說著名猶太歷史學家 Josephus有過以下的故事：在羅馬人占領喬塔帕特后，39個猶太人與 Josephus及他的朋友躲到?個洞中，39個猶太人決定寧愿死也不要被?抓到，于是決定了?個自殺方式，41個?排成?個圓圈，由第1個?開始報數，每報數到第3?該?就必須自殺，然后再由下? 個重新報數，直到所有?都自殺身亡為止。然?Josephus和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。】

題目：編號為 1?到 n?的 n?個人圍成一圈。從編號為 1?的人開始報數，報到 m?的人離開。

下一個人繼續從 1?開始報數。

n-1 輪結束以后，只剩下一個人，問最后留下的這個人編號是多少？

示例：輸入：5，2? ? ? ? ? 輸出：3

說明：

開始5個人 1，2，3，4，5 ，從1開始報數，1->1，2->2編號為2的人離開

1，3，4，5，從3開始報數，3->1，4->2編號為4的人離開

1，3，5，從5開始報數，5->1，1->2編號為1的人離開

3，5，從3開始報數，3->1，5->2編號為5的人離開

最后留下人的編號是3

思路：第一步：創建帶環鏈表第二步：計數

我們通過題意可知，是一個環形的，循環的鏈表，依然可以用雙指針法解決，創建兩個指針pcur,prev，pcur代表當前鏈表的節點，prev表示該節點的前一個節點，根據示例，一共有5個人，報數報到2的人要離開；prev開始的位置是在最后一個人即5的位置，pcur開始的位置就是1，走到下一步的時候就是2，是需要刪除（離開）的節點，刪除方式：pcur走到2時，此時的prev也要跟著走一步，到1的位置，改變prev的next指針的指向位置，即由 prev->next=pcur變成prev->next=pcur->next,然后就可以刪除pcur位置的節點；接著，此時pcur由刪除的節點位置繼續往下走，走向下一個有效的節點繼續從1開始報數，然后重復上述的操作

SLNode* creatCircle(int n)
{//先創建第一個節點SLNode* phead = newnode(1);SLNpde* ptail = phead;for(int i = 0;i <= n; i++){ptail->next = newnode(i);ptail = ptail->next;}//首尾相連，鏈表成環ptail->next = phead;return ptail;
}
int ysf(int n,int m)
{//1.根據n創建帶環鏈表SLNode* prev = creatCircle(n);SLNode* pcur = prev->next;int count = 1;//當鏈表中只有一個節點的情況 pcur->next == pcur,這個節點的數據就是留到最后的人while(pcur->next != pcur){if(count == m){//銷毀pcur節點prev->next = pcur->next;free(pcur);pcur = prev->next;count = 1;}else{//此時不需要銷毀節點prev = pcur;pcur = pcur->next;count++;}}//此時剩下的一個節點就是要返回的節點里的值int ret = pcur->val;free(pcur);pcur = NULL:return ret;
}

六、分割鏈表

給你一個鏈表的頭節點?phead?和一個特定值?x?，請你對鏈表進行分隔，使得所有?小于?x?的節點都出現在?大于或等于?x?的節點之前。

你不需要?保留?每個分區中各節點的初始相對位置。

(鏈表中節點的數目在范圍?[0, 200]?內)

示例：輸入：head = [1,4,3,2,5,2], x = 3? ? ? ? ??輸出：[1,2,2,4,3,5]

? ? ? ? ? ?輸入：head = [2,1], x = 2? ? ? ? ? ? ? ? ? ? ? 輸出：[1,2]

思路1：創建兩個新鏈表--小鏈表和大鏈表

將原鏈表中小于x的pcur節點的值尾插到小鏈表中，同時維護小鏈表的頭指針(lessHead)和尾指針(lessTail)

將原鏈表中大于或等于x的pcur節點的值尾插到大鏈表中，同時維護大鏈表的頭指針(greaterHead)和尾指針(greaterTail),最后將小鏈表的尾節點與大鏈表的第一個有效節點首尾相連

SLNode* partition(SLNode* phead,int x)
{//判空if(phead == NULL){return phead;}//創建兩個帶頭鏈表SLNode* lessHead,*lessTail;SLNode* greaterHead,*greaterTail;lessHead = lessTail = (SLNode*)malloc(sizeof(SLNode));greaterHead = greaterTail = (SLNode*)malloc(sizeof(SLNode));//遍歷原鏈表，將原鏈表中的節點尾插到大小鏈表中SLNode* pcur = phead;while(pcur){if(pcur->val < x){//尾插到小鏈表中lessTail->next = pcur;lessTail = lessTail->next;}else{//尾插到大鏈表中greaterTail->next = pcur;greaterTail = greaterTail->next;}pcur = pcur->next;}//修改大鏈表的尾節點的next指針指向(終止大鏈表)greaterTail->next = NULL;//若不加這一行，代碼會出現死循環+next指針初始化//小鏈表的尾節點和大鏈表的第一個有效節點首尾相連lessTail->next = greaterHead->next;//釋放SLNode* ret = lessHead->next;free(lessHead);free(greaterHead);lessHead = greaterHead = NULL;return ret;
}

測試空鏈表：

測試只有小于x或大于等于x的情況：

思路2：創建一個新鏈表

將原鏈表中若pcur節點的值小于x，頭插到新鏈表中，若pcur節點的值大于或等于x，尾插到新鏈表中，同時維護新鏈表的頭指針(newHead)和尾指針(newTail)，給新鏈表一個哨兵節點

SLNode* partition(SLNode* phead,int x)
{if(phead == NULL){return NULL;}//創建一個帶頭鏈表//創建哨兵節點作為新鏈表的頭SLNode* newHead,*newTail;newHead = newTail = (SLNode*)malloc(sizeof(SLNode));newHead->next = NULL;    SLNode* pcur = phead;while(pcur){//保存下一個節點SLNode* next = pcur->next;//在頭插操作時，pcur 的 next 會被修改if(pcur->val < x){//頭插到哨兵節點后面//要在哨兵節點newHead后面進行頭插，即在newHead->next節點位置開始進行頭插，而這個位置原本為NULL，即newHead,newHead->next=NULL=NULL//現在要變成 newHead,pcur,newHead->next=NULL,在NULL前面插入pcur，那么pcur->next就變成了NULL（pcur->next = newHead->next;）//哨兵節點的next節點就變成了pcur（newHead->next = pcur; ）pcur->next = newHead->next;newHead->next = pcur;//如果是第一個節點，需要更新newTailif(newTail == newHead){newTail = pcur;}}else{//尾插到鏈表末尾newTail->next = pcur;newTail = pcur;//newTail = newTail->next 更新尾指針 }pcur = next;}newTail->next = NULL;// 確保鏈表終止//釋放SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}

思路3：遍歷原鏈表，在原鏈表上進行修改

若pcur節點的值小于x，往后走，若pcur節點的值大于或等于x，尾插到原鏈表后，刪除舊節點

我們需要一個指針pcur，表示當前的節點，prev指針則表示當前節點的前一個節點（設置prev開始時的位置在哨兵節點上），pcur每走一步，prev就保存pcur前一步的位置，還需要一個ptail指針表示原鏈表的尾節點（ptail一直保持位置不變，表示原尾節點位置），一個newTail指針表示隨著每次尾插的變化的新的尾節點

當走到大于或等于x的節點位置時，修改prev的next指針的位置，即prev->next=pcur變成prev->next=pcur->next，然后將pcur節點尾插到原鏈表后面，newTail跟著移動，將舊的pcur節點刪除掉，再接著繼續往后走，重復以上的操作。

SLNode* partition(SLTNode* phead, int x)
{if(phead == NULL || phead->next == NULL) //鏈表為空或鏈表只有一個節點{return phead;}//1.找到原鏈表的尾節點SLNode* ptail = phead;while(ptail->next){ptail = ptail->next;}SLNode* newTail = ptail;//新的尾節點指針    //2.創建哨兵節點簡化操作SLNode* newHead = (SLNode*)malloc(sizeof(SLNode));newHead->next = phead;SLNode* prev = newHead;//前驅指針SLNode* pcur = phead;//當前指針//3.遍歷鏈表直到原始尾節點while(pcur != ptail){if(pcur->val < x){//保留當前節點，繼續前進prev = pcur;pcur = pcur->next;}else{//將當前節點移到鏈表末尾//從原位置移除當前節點prev->next = pcur->next;//將當前節點插入到末尾newTail->next = pcur;pcur->next = NULL;newTail = pcur;//更新新的尾節點//移動pcur到prev的下一個節點pcur = prev->next;//相當于pcur=pcur->next,但是不能這么寫，因為此時pcur->next 已經被設為 NULL，會導致錯誤}}//4.處理原始尾節點if(ptail->val >= x && ptail != newTail)//如果ptail已經是newTail（即已經被移動過一次），這個條件ptail != newTail可以防止重復移動{//如果原始尾節點需要移動prev->next = ptail->next;//實際上ptail->next是NULL,因為ptail是原始鏈表的尾節點，它的next本來就是NULLnewTail->next = ptail;ptail->next = NULL;newTail = ptail;}//5.釋放哨兵節點并返回結果SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}

其實不用處理尾節點也可以，因為到了尾節點的部分要么前面的節點包括尾節點本身都是小于x的，不用移動保持原樣，要么尾節點是大于等于x的，就尾插到當前鏈表的末尾

關鍵說明：為什么可以不需要單獨處理尾節點

當原始尾節點小于 x 時：
- 當?pcur?指向原始尾節點時，進入 if 分支
- 執行?prev = pcur?和?pcur = pcur->next
- 由于原始尾節點的?next?是?NULL，pcur?變為?NULL
- 循環條件?while(pcur != NULL)?不滿足，循環結束
當原始尾節點大于等于 x 時：
- 當?pcur?指向原始尾節點時，進入 else 分支
- 執行?prev->next = pcur->next（設置為?NULL）
- 執行?newTail->next = pcur（將節點移到末尾）
- 執行?pcur->next = NULL?和?newTail = pcur
- 執行?pcur = prev->next（變為?NULL）
- 循環條件?while(pcur != NULL)?不滿足，循環結束

SLNode* partition(SLNode* phead, int x)
{if(phead || phead->next){return phead;}SLNode* ptail = phead;while(ptail->next){ptail = ptail->next;}SLNode* newTail = ptail;SLNode* newHead = (SLNode*)malloc(sizeof(SLNode));newHead->next = phead;SLNode* prev = newHead;SLNode* pcur = phead;while(pcur){if(pcur->val > x){prev = pcur;pcur = pcur->next;}else{prev->next = pcur->next;newTail->next = pcur;pcur->next = NULL;newTail = pcur;pcur = prev->next;}}SLNode* ret = newHead->next;free(newHead);newHead = NULL;return ret;
}