C++相交鏈表和反轉鏈表詳解
給你兩個單鏈表的頭節點 headA 和 headB ,請你找出並返回兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點,返回 null 。
思路
簡單來說,就是求兩個鏈表交點節點的 指針。 這裡同學們要註意,交點不是數值相等,而是指針相等。
為瞭方便舉例,假設節點元素數值相等,則節點指針相等。
看如下兩個鏈表,目前curA指向鏈表A的頭結點,curB指向鏈表B的頭結點:
我們求出兩個鏈表的長度,並求出兩個鏈表長度的差值,然後讓curA移動到,和curB 末尾對齊的位置,如圖:
此時我們就可以比較curA和curB是否相同,如果不相同,同時向後移動curA和curB,如果遇到curA == curB,則找到焦點。
否則循環退出返回空指針。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { ListNode* curA=headA; ListNode* curB=headB; int lenA=0; int lenB=0; while(curA!=nullptr){ // 求鏈表A的長度 lenA++; curA=curA->next; } while(curB!=nullptr){ // 求鏈表B的長度 lenB++; curB=curB->next; } //現在的curA,curB已經指向最後一個節點瞭,需要重新指向頭結點 curA=headA; curB=headB; if(lenA<lenB){ //假設鏈表A的長度大於鏈表B,否則交換 swap(lenA,lenB); swap(curA,curB); } //gap是兩個鏈表長度的差值 int gap=lenA-lenB; // gap=lenA-lenB 錯誤,要有返回類型 while(gap){ // 讓curA和curB在同一起點上(末尾位置對齊) gap--; curA=curA->next; } while(lenB){ // 遍歷curA 和 curB,遇到相同則直接返回 if(curA==curB) return curA; // return curA(val) 返回節點中的值,這個寫法是錯誤的 直接return curA curA=curA->next; curB=curB->next; lenB--; } return nullptr; //沒有交點則返回空 } };
給你單鏈表的頭節點 head ,請你反轉鏈表,並返回反轉後的鏈表。
示例 1:
輸入:head = [1,2,3,4,5]
輸出:[5,4,3,2,1]
示例 2:
輸入:head = [1,2]
輸出:[2,1]
示例 3:
輸入:head = []
輸出:[]
雙指針思路
首先判斷鏈表是否為空,為空則返回nullptr。
接下來定義一個cur指針,指向頭結點,再定義一個pre指針,初始化為null。
然後就要開始反轉瞭,首先要把 cur->next 節點用tmp指針保存一下,也就是保存一下這個節點。
為什麼要保存一下這個節點呢,因為接下來要改變 cur->next 的指向瞭,將cur->next 指向pre ,此時已經反轉瞭第一個節點瞭。
接下來,就是循環走如下代碼邏輯瞭,繼續移動pre和cur指針。
最後,cur 指針已經指向瞭null,循環結束,鏈表也反轉完畢瞭。 此時我們return pre指針就可以瞭,pre指針就指向瞭新的頭結點。
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverseList(ListNode* head) { if(head==nullptr) //對空鏈表的判斷 return nullptr; ListNode* per=nullptr; ListNode* cur=head; ListNode* temp; //建立一個指針 while(cur){ //沒必要寫 while(cur!=nullptr),寫瞭這個還要判斷cur,會浪費時間,直接cur就可以 temp=cur->next; //保存cur的下一個節點 cur->next=per; //cur的下一個節點指向per,實現反轉 per=cur; //cur=per;錯誤,是把cur的節點賦值給per cur=temp; //temp=cur;錯誤,是把temp(原來的cur->next)的節點賦值給cur } return per; } };
遞歸
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* reverse(ListNode* per,ListNode* cur){ //返回的是一個鏈表,其返回值是指針 if(cur==nullptr) //遞歸的終止條件 return per; ListNode* temp=cur->next; cur->next=per; return reverse(cur,temp); // 調用要寫return } ListNode* reverseList(ListNode* head) { if(head==nullptr) //鏈表判空 return nullptr; return reverse(NULL,head); // 調用要寫return } };
總結
本篇文章就到這裡瞭,希望能給你帶來幫助,也希望您能夠多多關註WalkonNet的更多內容!