目錄

相交鏈表

反轉鏈表

?回文鏈表

環形鏈表?

合并兩個有序鏈表

---

相交鏈表

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if (headA == nullptr || headB == nullptr) {return nullptr;}ListNode *pA = headA;ListNode *pB = headB;while (pA != pB) {pA = (pA == nullptr)? headB : pA->next;pB = (pB == nullptr)? headA : pB->next;}return pA;}

顯然while循環是整個邏輯最重要的地方：這里使用了雙指針的方法。

1. 外層循環：while (pA != pB)?表示只要指針?pA?和?pB?沒有指向同一個節點，就持續循環。這是確保兩個指針不斷移動，直到找到相交節點或者確定沒有相交節點的控制條件。
2. pA?指針移動邏輯：pA = (pA == nullptr)? headB : pA->next;?這行代碼使用了條件運算符（三元運算符）。如果?pA?指向?nullptr，意味著?pA?已經遍歷完了它原本所在的鏈表，此時將?pA?重新指向鏈表?headB?的頭節點；否則，pA?就移動到當前節點的下一個節點。
3. pB?指針移動邏輯：pB = (pB == nullptr)? headA : pB->next;?與?pA?的移動邏輯類似。如果?pB?指向?nullptr，即?pB?遍歷完了它原本所在的鏈表，就將?pB?重新指向鏈表?headA?的頭節點；否則，pB?移動到當前節點的下一個節點。

通過這樣的邏輯，兩個指針會在相同的總步數下遍歷鏈表。如果兩個鏈表相交，它們最終會指向同一個相交節點；如果兩個鏈表不相交，那么?pA?和?pB?最終都會指向?nullptr，從而結束循環。

例如，假設有兩個鏈表?A?和?B，A?鏈表為?1 -> 2 -> 3 -> 6 -> 7，B?鏈表為?4 -> 5 -> 6 -> 7，pA?從?A?鏈表頭?1?開始，pB?從?B?鏈表頭?4?開始。當?pA?遍歷完?1 -> 2 -> 3?后指向?nullptr，此時重新指向?B?鏈表頭?4，繼續遍歷?4 -> 5，而?pB?遍歷完?4 -> 5?后指向?nullptr，重新指向?A?鏈表頭?1，繼續遍歷?1 -> 2 -> 3，最終?pA?和?pB?都會指向相交節點?6。

反轉鏈表

ListNode* reverseList(ListNode* head) {// 遞歸終止條件：如果當前節點為空或為尾節點，直接返回if (head == nullptr || head->next == nullptr) {return head;}// 遞歸處理當前節點的下一個節點ListNode* newHead = reverseList(head->next);// 回溯部分：反轉指針方向head->next->next = head;head->next = nullptr;return newHead;}

• 遞歸法：以節點為單位進行操作，從鏈表尾部開始反轉。函數接收當前節點作為參數，先遞歸調用自身處理當前節點的下一個節點，當到達鏈表尾部時返回該節點（作為新的頭節點）。然后在回溯過程中，將當前節點的下一個節點的?next?指針指向當前節點，并將當前節點的?next?指針置空，完成反轉操作。
  
  ?

?回文鏈表

bool isPalindrome(ListNode* head) {bool b=true;std::vector<int> temp;ListNode* p=head;while(p!=nullptr){temp.push_back(p->val);p = p->next;}int n = temp.size();for (int i = 0; i < n / 2; ++i) {if (temp[i] != temp[n - 1 - i]) {return false;}}return b;}

好吧，通過很笨的辦法，把鏈表弄到數組里，然后兩個指針依次比較q_q

環形鏈表?

bool hasCycle(ListNode *head) {std::unordered_set<ListNode*> visited;ListNode* curr = head;while (curr != nullptr) {// 如果節點已在哈希表中，說明有環if (visited.find(curr) != visited.end()) {return true;}// 將當前節點加入哈希表visited.insert(curr);// 移動到下一個節點curr = curr->next;}// 遍歷完鏈表無重復，說明無環return false;}

?好吧，依舊是簡單粗暴，直接丟哈希表里面，然后通過哈希表現有的函數直接去檢查是否沖突
?

合并兩個有序鏈表

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummy=new ListNode();ListNode* curr=dummy;ListNode* p1=list1;ListNode* p2=list2;while(p1!=nullptr&&p2!=nullptr){if(p1->val<p2->val){curr->next=p1;p1=p1->next;}else{curr->next=p2;p2=p2->next;}curr=curr->next;}curr->next=(p1!=nullptr)?p1:p2;ListNode* result=dummy->next;delete dummy;return result;}

?這里使用了迭代法，依舊是簡單無腦遍歷，通過兩個指針比大小，小的就先放進去。嗯就這樣。