前言

這次將要把剩下的oj題將以圖解和自己的理解把它講解完，希望對大家有所幫助，這次的講解也是干貨

第一題

21. 合并兩個有序鏈表 - 力扣（LeetCode）

ok這次就簡單點，大家自己去看題目了

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

暴力思路

想想看不考慮空間和時間的消耗，什么代碼最容易想

兩個鏈表，可不可以直接把兩個鏈表的值放在一個數組中

然后再排序，當然這里的鏈表大小是有序的，放在數組中時

可以判斷大小，從而不用去排序

再根據數組自行去malloc一個鏈表，是不是非常暴力的思路

這個暴力代碼其實也很重要，至少是算法小白入門的絕招

#include<stdio.h>
#include<stdlib.h>
typedef struct SlistNode {struct SlistNode* next;int val;
}SLNode,*SL;
SLNode* Buyslistnode(int data)
{SL newnode = (SL)malloc(sizeof(SLNode));newnode->next = NULL;newnode->val = data;return newnode;
}
SL initlist1()
{SL list1 = (SL)malloc(sizeof(SLNode));list1->val = 1;list1->next = Buyslistnode(2);list1->next->next = Buyslistnode(4);return list1;
}
SL initlist2()
{SL list2 = (SL)malloc(sizeof(SLNode));list2->val = 1;list2->next = Buyslistnode(3);list2->next->next = Buyslistnode(4);return list2;
}
int cmp(const void* p1, const void* p2)
{return *(int*)p1 - *(int*)p2;
}
void text1()
{//我們這里直接考慮list1與list2都不是空鏈表的情況//其實其他的情況可以通過if判斷排除//初始化題目//list1   1->2->4//list2   1->3->4SL list1 = initlist1();SL list2 = initlist2();//題目中鏈表的結點數是0~50//所以直接可以用靜態數組int newarr[110];int size = 0;while (list1){newarr[size++] = list1->val;list1 = list1->next;}while (list2){newarr[size++] = list2->val;list2 = list2->next;}qsort(newarr, size, sizeof(int), cmp);SL phead = (SL)malloc(sizeof(SLNode));SL cur = phead;for (int i = 0; i < size; i++){cur->next = Buyslistnode(newarr[i]);cur = cur->next;}//至此已經完成//打印看結果吧cur = phead->next;while (cur){printf("%d ", cur->val);cur = cur->next;}
}
int main()
{text1();return 0;
}

那么看結果

OK接下來看看優化的思路 頭結點+雙頭插

對于這個例子

我們一第二條鏈表為基礎對他進行插入操作

我們使用兩個指針，分別指向兩條鏈表的第一個位置cur1 cur2

如果第一個鏈表的值小于第二個鏈表的值那么尾插到此時第二個鏈表指針的前面

cur1->val<=cur2->val? ? ??

并且讓第一個指針cur1=cur1->next;

當然這里只是大題思路不是代碼

如果大于?cur1->val>cur2->val? ?

那么讓cur2=cur2->next

在進行操作的時候，我們為了避免在第一個位置插入?，從而加入了頭指針

OK，看代碼唄

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {if(list1==NULL&&list2==NULL)return list1;else if(list1!=NULL&&list2==NULL)return list1;else if(list1==NULL&&list2!=NULL)return list2;struct ListNode*p1=list1;struct ListNode*p2=list2;struct ListNode*p2head=(struct ListNode*)malloc(sizeof(struct ListNode));p2head->next=p2;struct ListNode*front=p2head;while(p1&&p2){if(p1->val<=p2->val){//雙指針中間插入//front->next=p1;struct ListNode*temp=p1;p1=p1->next;temp->next=p2;front=temp;}else{front=p2;p2=p2->next;}}//如果p2==null此時p1不為空，把p1接起來if(p2==NULL)front->next=p1;return p2head->next;}

?第二題

現有一鏈表的頭指針 ListNode*?pHead，給一定值x，編寫一段代碼將所有小于x的結點排在其余結點之前，且不能改變原來的數據順序，返回重新排列后的鏈表的頭指針。

鏈表分割_牛客題霸_牛客網 (nowcoder.com)

ok

這個題目其實也可以暴力

但是

已經寫了好多次暴力了，對吧

這一次可以說說思路

仍然可以使用數組，然后直接排序，不管x為多少，按從小到大的順序，沒有錯

然后構建鏈表，這個題目就完了

挺暴力的吧

可以的

但是這個代碼和之前大差不差

直接來看具體的思路

我們可以把一個鏈表分成兩個鏈表，list1一個是大于等于x的，list2一個是小于x的

最后讓list2連接list1

就完成任務了

思路看起來簡單但是細節還是很多

我們在代碼中有注釋

class Partition {
public:ListNode* partition(ListNode* pHead, int x) {if(pHead==NULL&&pHead->next==NULL)return pHead;auto *head=(ListNode*)malloc(sizeof(ListNode));head->next=pHead;//頭結點ListNode*front=head;ListNode*newlist=NULL;ListNode*newtail=NULL;ListNode*p=pHead;while(p){if(p->val<x){//在原有的鏈表上去除小于x的值ListNode*temp=p;p=p->next;temp->next=NULL;front->next=p;//對新的鏈表操作//小于x的值重新連成一個鏈表if(newlist==NULL){newlist=newtail=temp;}else{newtail->next=temp;newtail=temp;}}else {front=p;p=p->next;  }}//不要忘了呀，新的鏈表有可能為空呀，哎呦，搞了個半天if(newtail==NULL)return pHead;elsenewtail->next=head->next;return newlist;}
};

這個題目思路還是不難，繼續努力

第三題

鏈表的回文結構_牛客題霸_牛客網 (nowcoder.com)

對于一個鏈表，請設計一個時間復雜度為O(n),額外空間復雜度為O(1)的算法，判斷其是否為回文結構。

給定一個鏈表的頭指針A，請返回一個bool值，代表其是否為回文結構。保證鏈表長度小于等于900。

1->2->2->1

返回：true

這個題目有難度了

所以我們可以通過畫圖來理解一下

思路，

我們可以找到中間的結點，把中間的結點逆置過來

然后一個指針從中間

另一個指針從開頭

一直判斷他們是否相等，就可以得到答案

看圖唄

?OK，找中以及逆轉鏈表之前已經有過講解了

單鏈表的經典oj題(1)-CSDN博客

好吧，不懂可以去看

我們現在直接去看代碼嘍

 ListNode*middle(ListNode*A){ListNode*slow=A;ListNode*fast=A;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;}return slow;}ListNode* revearse(ListNode*src){ListNode* cur=src;ListNode* prev=NULL;while(cur){ListNode* temp=cur->next;cur->next=prev;prev=cur;cur=temp;}return prev;}bool chkPalindrome(ListNode* A) {// write code hereListNode*cur=middle(A);ListNode* tail=revearse(cur);while(A&&tail){if(tail->val!=A->val)return false;tail=tail->next;A=A->next;}return true;}

第四題

給你兩個單鏈表的頭節點?headA?和?headB?，請你找出并返回兩個單鏈表相交的起始節點。如果兩個鏈表不存在相交節點，返回?null?

題目在這里

160. 相交鏈表 - 力扣（LeetCode）

OK

思路

?首先要判斷他們是否是有相交節點

OK可以讓他們走到最后一個節點

如果他們的最后一個節點相等，那他們就有相交節點，那么問題來了

怎么找到節點呢

要是知道兩個鏈表的長度，再利用相對位移讓他們距離相交節點的位移一樣

最后讓他們同時走，再判斷，直到相等即可

OK

看代碼

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode*A =headA;struct ListNode*B =headB;//這里最后一個節點沒有加上，所以初始為1int sizeA=1;int sizeB=1;while(A->next){A=A->next;sizeA++;}while(B->next){B=B->next;sizeB++;}if(A!=B)return NULL;//通過假設，來簡化代碼//總之就是讓A最長if(sizeA<sizeB){A=headB;B=headA;}else{A=headA;B=headB;}int abs=sizeA-sizeB>0?sizeA-sizeB:sizeB-sizeA;//使他們里相交點的距離相等while(abs--){A=A->next;}while(A!=B){A=A->next;B=B->next;}return B;
}

第五題?

?141. 環形鏈表 - 力扣（LeetCode）

題目

給你一個鏈表的頭節點?head?，判斷鏈表中是否有環。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。注意：pos?不作為參數進行傳遞?。僅僅是為了標識鏈表的實際情況。

如果鏈表中存在環?，則返回?true?。 否則，返回?false?。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個環，其尾部連接到第二個節點

OK

這個題目的思路很重要，我這里有兩種做法

暴力求解

如果只要求求出題目，那么我們可不可以用一個數據來標明這個節點走過沒有

• -10^5 <= Node.val <= 10^5

當我們走過一個結點

直接給他加上一個10^6+10

+10是防止特殊情況，那么只要遍歷一遍，走到某個節點，如果它大于

10^5證明我們走過這里，但是此時又回到了這里，此時可以判斷為有環

缺點是破壞了鏈表

bool hasCycle(struct ListNode *head) {while(head){if(head->val>1e5)return true;else{head->val+=1e6+10;}head=head->next;}return false;
}

這種辦法還是挺有意思的不是嗎？

OK

來看看不改變鏈表的結構的寫法吧

這個還是要畫圖理解，并且這里還是涉及到了相對位置的概念

bool hasCycle(struct ListNode *head) 
{struct ListNode * slow = head ;struct ListNode * fast = head ;while(fast && fast->next){fast = fast->next->next;slow = slow->next;if(slow == fast)return true;}return false;}

話不多說下一題

第六題

142. 環形鏈表 II - 力扣（LeetCode）

?這個題目，是上個題目的升級版

OK看題

給定一個鏈表的頭節點 ?head?，返回鏈表開始入環的第一個節點。?如果鏈表無環，則返回?null。

如果鏈表中有某個節點，可以通過連續跟蹤?next?指針再次到達，則鏈表中存在環。 為了表示給定鏈表中的環，評測系統內部使用整數?pos?來表示鏈表尾連接到鏈表中的位置（索引從 0 開始）。如果?pos?是?-1，則在該鏈表中沒有環。注意：pos?不作為參數進行傳遞，僅僅是為了標識鏈表的實際情況。

不允許修改?鏈表。

示例 1：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節點
解釋：鏈表中有一個環，其尾部連接到第二個節點。

思路

大家看這里就是不允許修改鏈表了

這該如何是好

還是畫圖吧

這個題目更是一個物理的模型

OK，看代碼吧

struct ListNode *detectCycle(struct ListNode *head) {struct ListNode*slow=head;struct ListNode*fast=head;struct ListNode*meet=NULL;struct ListNode*find=head;while(fast&&fast->next){fast=fast->next->next;slow=slow->next;if(fast==slow){meet=slow;break;}}if(meet==NULL)return NULL;while(find!=meet){find=find->next;meet=meet->next;}return find;
}

總結

今天的題還是挺多的，好好練吧