樂觀學習，樂觀生活，才能不斷前進啊！！！

我的主頁：optimistic_chen
我的專欄：c語言
點擊主頁：optimistic_chen和專欄：c語言，
創作不易，大佬們點贊鼓勵下吧~

合并兩個有序鏈表

合并兩個有序鏈表———力扣

第一種思路

直接創建一個空鏈表，分別判斷兩個原鏈表的元素大小，升序插入到新鏈表中，但是此方法可能會超出時間限制（每一次都需要判斷新鏈表的頭節點是否為空），代碼重復執行太多。

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判斷為空鏈表if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* l1=list1;ListNode*l2=list2;//創建的新鏈表ListNode*newHead,*newTail;newHead=newTail=NULL;while(l1&&l2){if(l1->val < l2->val){//l1拿下來尾插if(newHead==NULL){newHead=newTail=l2;}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(l2){newTail->next=l2;}if(l1){newTail->next=l1;}return newHead;
}

第二種思路

優化：讓新鏈表不為空，判斷兩個原鏈表元素大小后，直接插入到新鏈表中

typedef struct ListNode ListNode;
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {//判斷為空鏈表if(list1==NULL){return list2;}if(list2==NULL){return list1;}ListNode* l1=list1;ListNode*l2=list2;//創建的新鏈表(鏈表不為空)ListNode*newHead,*newTail;//newHead=newTail=NULL;newHead=newTail=(ListNode*)malloc(sizeof(ListNode));while(l1&&l2){if(l1->val < l2->val){//l1拿下來尾插newTail->next=l1;newTail=newTail->next;l1=l1->next;}else{//l2拿下來尾插newTail->next=l2;newTail=newTail->next;l2=l2->next;}}//跳出循環，要么l1先為空，要么l2先為空if(l2){newTail->next=l2;}if(l1){newTail->next=l1;}//動態申請的空間要手動釋放掉ListNode* ret=newHead->next;free(newHead);newHead=NULL;return ret;
}

環形鏈表的約瑟夫問題

環形鏈表的約瑟夫問題——牛客網

環形鏈表與我們平時見到的鏈表不同的是：他的尾節點的next指針指向頭節點，而不是NULL。

typedef struct ListNode ListNode;//創建節點ListNode*buyNode(int x){ListNode*node=(ListNode*)malloc(sizeof(ListNode));if(node==NULL){exit(1);}node->val=x;node->next=NULL;return node;}ListNode*createCircle(int n){//先創建第一個節點ListNode*phead=buyNode(1);ListNode*ptail=phead;for(int i=2;i<=n;i++){ptail->next=buyNode(i);ptail=ptail->next;}//首位相連ptail->next=phead;return ptail;} 
int ysf(int n, int m ) {//第一步，根據n創建帶環鏈表ListNode*prev=createCircle(n);ListNode*pcur=prev->next;//第二步記數int count=1;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++;}}//此時剩下的一個節點就是要返回的值return pcur->val;}

分割鏈表

分割鏈表——力扣

第一種思路

雙指針法：
1.創建大，小兩個新鏈表。
2.將小于特定值的節點放到小鏈表中，將大于等于特定值的節點放到大鏈表中
3.小鏈表的尾節點和大鏈表的第一個有效節點首尾相連

typedef struct ListNode ListNode;
struct ListNode* partition(struct ListNode* head, int x){if(head==NULL){return head;}//創建兩個帶頭鏈表ListNode*lessHead,*lessTail;ListNode*greaterHead,*greaterTail;lessHead=lessTail=(ListNode*)malloc(sizeof(ListNode));greaterHead=greaterTail=(ListNode*)malloc(sizeof(ListNode));//遍歷原鏈表，將原鏈表中的節點尾插到大小鏈表中ListNode*pcur=head;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;//小鏈表的尾節點和大鏈表的第一個有效節點首尾相連lessTail->next=greaterHead->next;ListNode*ret=lessHead->next;free(lessHead);free(greaterHead);lessHead=greaterHead=NULL;return ret;
}

第二種思路

HeadNode哨兵結點：用于頭插；Tail尾指針用于尾插；cur表示當前鏈表結點；
遍歷鏈表依次用鏈表結點元素值與X比較；小于則頭插；大于則尾插；
這里有一個小細節就是頭插時，如果尾指針等于哨兵HeadNode則需更新Tail指向尾結點

struct ListNode* partition(struct ListNode* head, int x){struct ListNode* HeadNode=(struct ListNode*)malloc(sizeof(struct ListNode));struct ListNode* Tail=HeadNode,*cur=head;Tail->next=NULL;while(cur){struct ListNode* next=cur->next;if(cur->val<x){cur->next=HeadNode->next;HeadNode->next=cur;if(Tail==HeadNode){Tail=cur;}}else{Tail->next=cur;Tail=cur;cur->next=NULL;}cur=next;}return HeadNode->next;
}

完結

好了，這期的分享到這里就結束了~
如果這篇博客對你有幫助的話，可以點一個免費的贊并收藏起來喲~
可以點點關注，避免找不到我~
我們下期不見不散~~
這個鏈表題目還會繼續，敬請期待~