一、相交鏈表問題

問題描述

給定兩個單鏈表，判斷它們是否相交，若相交則返回相交的節點。（注意：判斷依據是節點地址是否相同，而非節點值，因為節點值可能存在重復。）

---

解題思路分析

思路一：暴力遍歷法

• 方法：遍歷鏈表A，對于A中的每一個節點，遍歷整個鏈表B，檢查是否存在地址相同的節點。
• 時間復雜度：O(M*N)（若兩鏈表長度分別為M和N）
• 空間復雜度：O(1)
• 缺點：效率低，不適用于長鏈表。

思路二：雙指針對齊法（最優解）

• 方法：
  1. 分別遍歷兩個鏈表，計算各自長度。
  2. 求出兩鏈表長度差 gap。
  3. 讓較長的鏈表的指針先移動 gap 步。
  4. 然后兩個指針同時移動，逐個比較節點地址，第一個相同的節點即為交點。
• 時間復雜度：O(M + N)
• 空間復雜度：O(1)
• 優點：高效，適用于任意長度的鏈表。

思路2的時間復雜度更低，所以我們選擇思路2

具體代碼如下

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode* curA=headA,*curB=headB;int lenA=1,lenB=1;while(curA->next){curA=curA->next;lenA++;}while(curB->next){curB=curB->next;lenB++;}int gap=abs(lenA-lenB);//假設法 先假設A長struct ListNode* longList=headA;struct ListNode* shortList=headB;if(lenA<lenB){longList=headB;shortList=headA;}while(gap--){longList=longList->next;}while(longList){if(longList==shortList)return longList;longList=longList->next;shortList=shortList->next;}return NULL;
}

二、鏈表的回文結構

問題描述

判斷一個單鏈表是否為回文結構。即正著讀和反著讀都一樣

解題思路

回文鏈表判斷的關鍵在于對稱性驗證。我們可以通過以下步驟實現：

1. 找到中間節點：使用快慢指針法，快指針每次走兩步，慢指針每次走一步，當快指針到達末尾時，慢指針正好在中間。
2. 反轉后半部分鏈表：從中間節點開始，將后半部分鏈表反轉。
3. 比較前后兩部分：從頭節點和反轉后的中間節點開始，逐個比較節點值是否相同。

完整代碼

class PalindromeList {
public://尋找中間節點
struct ListNode* middleNode(struct ListNode* head) {// 初始化快慢指針struct ListNode* slow = head;struct ListNode* fast = head;// 移動指針直到fast到達鏈表末尾while (fast != NULL && fast->next != NULL) {slow = slow->next;      // 慢指針每次移動一步fast = fast->next->next; // 快指針每次移動兩步}return slow; // 慢指針指向中間節點
}//反轉鏈表
struct ListNode* reverseList(struct ListNode* head) {struct ListNode* n1, *n2, *n3;n1 = NULL;n2 = head;if (n2)n3 = n2->next;while (n2) {n2->next = n1;n1 = n2;n2 = n3;if (n3)n3 = n3->next;}return n1;
}bool chkPalindrome(ListNode* A) {// write code herestruct ListNode*mid=middleNode(A);struct ListNode*rmid=reverseList(mid);while(rmid&&A){if(rmid->val!=A->val)return false;rmid=rmid->next;A=A->next;}return true;
}};

三、 隨即鏈表的復制

問題描述

實現一個函數，復制一個含有隨機指針的鏈表。隨機指針可以指向鏈表中的任何節點或為空。

解題思路

常規鏈表的復制很簡單，但隨機指針的存在使得問題復雜化。因為隨機指針可能指向尚未復制的節點。我們可以通過以下三步解決：

1. 插入拷貝節點：在原鏈表的每個節點后插入一個拷貝節點，值與原節點相同。
2. 設置隨機指針：拷貝節點的隨機指針應指向原節點隨機指針所指節點的下一個節點（即其拷貝）。
3. 分離鏈表：將混合鏈表分離為原鏈表和拷貝鏈表。

struct Node* copyRandomList(struct Node* head) {//拷貝節點插到原節點后邊
struct Node*cur=head;while(cur)
{struct Node* copy=(struct Node*)malloc(sizeof(struct Node));//分配內存copy->next=cur->next;cur->next=copy;copy->val=cur->val;cur=copy->next;//cur走到原鏈表的下一個  
}
//控制randomcur=head;
while(cur)
{struct Node* copy = cur->next;if(cur->random==NULL)//不要寫成random==NULL{copy->random=NULL;}else{copy->random=cur->random->next;//核心代碼}cur=copy->next;
}//把拷貝鏈表尾插起來
struct Node* copyhead=NULL,*copytail=NULL;cur=head;
while(cur)
{struct Node*copy=cur->next;if(copytail==NULL){copyhead=copytail=copy;}else{copytail->next=copy;copytail=copytail->next;}cur=copy->next;
}
return copyhead;
}

復雜度分析

• 時間復雜度：O(N)，三次遍歷鏈表。
• 空間復雜度：O(1)，除了返回的拷貝鏈表外，僅使用了常數個額外指針。