題目一：鏈表中環的入口節點

????這道題的有如下三個關鍵點：
（1）判斷鏈表中是否存在環；
（2）找出環的長度；
（3）快慢指針遍歷鏈表得到相遇節點，該相遇節點即為環入口。
????首先對于環的存在性判斷，可以使用快慢指針，一開始讓front指針和end指針都指向第一個節點，接下來慢指針每次向前移動1個節點，快節點每次向前移動2個節點，這樣快指針每次都會比慢指針多走1個節點，如果鏈表中存在環，那么存在一種情況，快指針比慢指針多走k*n，其中k表示一個正整數，n為環的長度。
????接下來便是找出環的長度了，在第一次快慢指針相遇之后，讓快慢指針按照之前的方式接著向前走，最后快慢指針會第二次相遇，此時便有快指針比慢指針多走的長度就是鏈表中環長。
????最后，調整依次快慢指針的開始位置，快慢指針都設置成第一個節點，接著快指針向前走環長，然后快慢指針一起向前走，下一次相遇說明便找到了入口節點了。最終得到如下代碼：

# include <iostream>
# include <algorithm>
using namespace std;
struct linkNode {int data;linkNode * next;linkNode(int val):data(val),next(nullptr) {}
};
typedef linkNode * linkList;linkList createLinkList(int arr[],int len) {//使用空頭鏈表linkList head=new linkNode(0),q=head;for(int i=0; i<len; ++i) {linkNode * p=new linkNode(arr[i]);q->next=p;q=p;}q->next=nullptr;return head;
}void mockCircle(linkList head) {linkList p=head;linkNode * q=nullptr,*last=nullptr;while(p!=nullptr) {if(p->data==3) {q=p;}if(p->next==nullptr) {last=p;}p=p->next;}last->next=q;
}linkNode* findCircleEnter(linkList head) {linkNode *front=head->next,*end=head->next;int count=1;while(front!=nullptr&&end!=nullptr&&front!=end) {front=front->next;if(end->next) {end=end->next->next;} else {end!=nullptr;}}if(end==nullptr) {return nullptr;} else {front=front->next;end=end->next->next;while(front!=end) {front=front->next;end=end->next->next;count++;}cout<<"輸出環長："<<count<<endl;front=head->next;end=head->next;while(count--) {end=end->next;}while(front!=end) {front=front->next;end=end->next;}return end;}
}int main() {int arr[]= {1,2,3,4,5,6};linkList head= createLinkList(arr,6);mockCircle(head);cout<<"輸出入口節點的值："<<findCircleEnter(head)->data<<endl;return 0;
}

????補充說明，實際代碼應該沒有這里長，通常算法只需要寫findCircleEnter函數，但是為了方便去模擬這個查找過程，這里根據圖例構造了帶環模擬鏈表（帶有空頭鏈表）。這里的時間復雜度也比較好，站在front的角度，一開始為了得到環的長度，只需要遍歷一次鏈表，然后找入口節點，總和來看最多遍歷兩次鏈表，因此總的時間復雜度為O(n)。

題目二：兩個鏈表的第1個重合節點

????依稀記得這是考研408中的一道真題，相較于前面的題目而言，這道題的難度稍顯簡單。這道題的解題關鍵在于統一起點，然后讓兩個鏈表一起向后遍歷。具體的操作步驟是，首先分別對兩個鏈表的長度進行一次統計，這樣便能清晰知曉兩個鏈表長度的差異。接著，使用兩個指針，讓它們各自指向兩個鏈表的第一個節點，此時，根據之前統計得到的鏈表長度，讓長度較長的鏈表的指針先走gap個節點。例如，若長鏈表的長度為m，短鏈表的長度為n，那么gap的值就是兩者的差值，即n-m。通過這樣的方式，使得兩個鏈表的指針處于相對統一的起始位置，以便后續的遍歷操作。基于上述思路，于是便可以得到如下的代碼來實現相應的功能。

# include <iostream>
# include <algorithm>
using namespace std;
struct linkNode {int data;linkNode * next;linkNode(int val):data(val),next(nullptr) {}
};
typedef linkNode * linkList;linkList createLinkList(int arr[],int len) {//使用空頭鏈表linkList head=new linkNode(0),q=head;for(int i=0; i<len; ++i) {linkNode * p=new linkNode(arr[i]);q->next=p;q=p;}q->next=nullptr;return head;
}
void mockCircle(linkList head1,linkList head2) {linkList p1=head1->next,p2=head2->next;linkNode * q=nullptr;while(p1!=nullptr) {if(p1->data==4) {q=p1;}p1=p1->next;}while(p2->next!=nullptr) {p2=p2->next;}p2->next=q;
}linkNode* findCommon(linkList head1,linkList head2) {int count1=0,count2=0,gap=0;linkNode * p1=head1, *p2=head2,*p=head1->next,*q=head2->next;while(p1->next) {//統計head1鏈表長度 p1=p1->next;count1++;}while(p2->next) {//統計head2鏈表長度p2=p2->next;count2++;}while(count1>count2) {//拉齊鏈表起點 p=p->next;count1--;}while(count2>count1) {q=q->next;count2--;}while(p!=q){p=p->next;q=q->next;}return q;
}int main() {int arr1[]= {1,2,3,4,5,6};int arr2[]= {7,8};linkList head1= createLinkList(arr1,6);linkList head2= createLinkList(arr2,2);mockCircle(head1,head2);cout<<"輸出公共節點對應的值："<<findCommon(head1,head2)->data<<endl;return 0;
}

????同樣的，實際編碼的時候只需要寫findCommon即可。

題目三：反轉鏈表

????在數據結構與算法的學習和考察中，鏈表相關的題目一直是重點內容，而本題基本上算得上是鏈表系列的必考題。因為鏈表反轉操作在實際的編程場景，如操作系統底層數據處理、圖形渲染中的節點順序調整等方面經常會被使用到。對于這道題，其解題的一個非常關鍵的思路是，將指針pre初始化為null。這樣做的目的在于為后續鏈表節點指針方向的改變提供一個起始參照。在每次循環過程中，巧妙地改變指針的指向，從而逐步實現鏈表的反轉。每一次指針方向的調整，都是對鏈表原有結構的一次重塑，通過這種循環操作，最終能夠將整個鏈表的順序反轉過來。最終得到的代碼如下：

# include <iostream>
# include <algorithm>
using namespace std;
struct linkNode {int data;linkNode * next;linkNode(int val):data(val),next(nullptr) {}
};
typedef linkNode * linkList;linkList createLinkList(int arr[],int len) {//使用空頭鏈表linkList head=new linkNode(0),q=head;for(int i=0; i<len; ++i) {linkNode * p=new linkNode(arr[i]);q->next=p;q=p;}q->next=nullptr;return head;
}void printLinkList(linkList head) {linkList p=head->next;while(p!=nullptr) {cout<<p->data<<" ";p=p->next;}
}
void reverseList(linkList head) {linkNode * pre=nullptr,*cur=head->next,*next=nullptr,*last=nullptr;while(cur) {if(!cur->next) {//因為存在空頭，所以在真實元素反轉后，需要讓頭指向最后一個節點last=cur;}next=cur->next;cur->next=pre;pre=cur;cur=next;}head->next=last;
}int main() {int arr1[]= {1,2,3,4,5};linkList head= createLinkList(arr1,5);reverseList(head);cout<<"輸出反轉之后的鏈表：";printLinkList(head);return 0;
}

附錄：源碼gitee倉庫

????考慮到有些算法需要模擬數據，如果全部放進來代碼顯得過長，不利于聚焦在算法的核心思路上。于是把所有的代碼整理到了開源倉庫上，如果想要看詳細模擬數據，可在開源倉庫自取：【凌空暗羽/劍指offer-C++版手寫代碼】。

????我是【Jerry說前后端】，本系列精心挑選的算法題目全部基于經典的《劍指 Offer（數據結構與算法面試題精講）》。在如今競爭激烈的技術求職環境下，算法能力已成為前端開發崗位筆試考核的關鍵要點。通過深入鉆研這一系列算法題，大家能夠系統地積累算法知識和解題經驗。每一道題目的分析與解答過程，都像是一把鑰匙，為大家打開一扇通往高效編程思維的大門，幫助大家逐步提升自己在數據結構運用、算法設計與優化等方面的能力。
????無論是即將踏入職場的應屆畢業生，還是想要進一步提升自己技術水平的在職開發者，掌握扎實的算法知識都是提升競爭力的有力武器。希望大家能跟隨我的步伐，在這個系列中不斷學習、不斷進步，為即將到來的前端筆試做好充分準備，順利拿下心儀的工作機會！快來訂閱吧，讓我們一起開啟這段算法學習之旅！