1兩兩交換鏈表中的節(jié)點(diǎn)

給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。

示例 1：

輸入：head = [1,2,3,4]
輸出：[2,1,4,3]

示例 2：

輸入：head = []
輸出：[]

示例 3：

輸入：head = [1]
輸出：[1]

提示：

• 鏈表中節(jié)點(diǎn)的數(shù)目在范圍?[0, 100]?內(nèi)
• 0 <= Node.val <= 100

思路：

初始檢查：如果鏈表為空或只有一個(gè)節(jié)點(diǎn)，直接返回。

創(chuàng)建虛擬頭節(jié)點(diǎn)：使用一個(gè)虛擬頭節(jié)點(diǎn) dummy 來(lái)簡(jiǎn)化邊界情況的處理。

循環(huán)交換節(jié)點(diǎn)對(duì)：在鏈表中繼續(xù)交換每一對(duì)節(jié)點(diǎn)，直到?jīng)]有更多的節(jié)點(diǎn)對(duì)（cur->next && cur->next->next 都不為空時(shí)）可以交換。開(kāi)始時(shí)cur為與虛擬頭結(jié)點(diǎn)位置

步驟一：cur->next 指向第二個(gè)節(jié)點(diǎn)。

步驟二：第二個(gè)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)。

步驟三：第一個(gè)節(jié)點(diǎn)的 next 指向第三個(gè)節(jié)點(diǎn)。

移動(dòng)到下一對(duì)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)：將 cur 移動(dòng)到下一對(duì)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

代碼：

struct ListNode* swapPairs(struct ListNode* head) {// 如果鏈表為空或只有一個(gè)節(jié)點(diǎn)，直接返回if (!head || !head->next) return head;struct ListNode dummy;  // 創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)dummy.next = head;struct ListNode* cur = &dummy;while (cur->next && cur->next->next) {struct ListNode* tmp = cur->next;         // 保存第一個(gè)節(jié)點(diǎn)struct ListNode* tmp1 = cur->next->next->next;  // 保存第二個(gè)節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)cur->next = cur->next->next;    // 步驟一：cur->next 指向第二個(gè)節(jié)點(diǎn)cur->next->next = tmp;          // 步驟二：第二個(gè)節(jié)點(diǎn)的 next 指向第一個(gè)節(jié)點(diǎn)cur->next->next->next = tmp1;   // 步驟三：第一個(gè)節(jié)點(diǎn)的 next 指向第三個(gè)節(jié)點(diǎn)cur = cur->next->next;  // 移動(dòng)到下一對(duì)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)}return dummy.next;  // 返回新的頭節(jié)點(diǎn)
}

2刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

給你一個(gè)鏈表，刪除鏈表的倒數(shù)第?n?個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。

示例 1：

輸入：head = [1,2,3,4,5], n = 2
輸出：[1,2,3,5]

示例 2：

輸入：head = [1], n = 1
輸出：[]

示例 3：

輸入：head = [1,2], n = 1
輸出：[1]

提示：

• 鏈表中結(jié)點(diǎn)的數(shù)目為?sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

思路：

1. 創(chuàng)建虛擬頭節(jié)點(diǎn)：使用?malloc?分配內(nèi)存并創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)?dummy，其?val?為 0，next?指向?qū)嶋H的頭節(jié)點(diǎn)?head。
2. 初始化快慢指針：fast?和?slow?都指向虛擬頭節(jié)點(diǎn)。
3. 快指針先移動(dòng) n 步：通過(guò)循環(huán)，讓?fast?指針先移動(dòng)?n?步。
4. 快指針再移動(dòng)一步：因?yàn)樾枰宻low指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)
5. 同時(shí)移動(dòng)快慢指針：繼續(xù)移動(dòng)?fast?和?slow?指針，直到?fast?指針到達(dá)鏈表末尾。此時(shí)，slow?指針指向的節(jié)點(diǎn)就是要?jiǎng)h除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。
6. 刪除節(jié)點(diǎn)：將?slow?的?next?指向?slow->next->next，從而刪除目標(biāo)節(jié)點(diǎn)。
7. 更新頭節(jié)點(diǎn)：將?head?更新為?dummy->next。
8. 釋放虛擬頭節(jié)點(diǎn)：使用?free?釋放虛擬頭節(jié)點(diǎn)的內(nèi)存空間。
9. 返回頭節(jié)點(diǎn)：返回更新后的頭節(jié)點(diǎn)?head。

代碼：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     struct ListNode *next;* };*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {// 創(chuàng)建一個(gè)虛擬頭節(jié)點(diǎn)，并初始化其值為0，next指向?qū)嶋H的頭節(jié)點(diǎn)struct ListNode* dummy = malloc(sizeof(struct ListNode));dummy->val = 0;dummy->next = head;// 初始化快慢指針，都指向虛擬頭節(jié)點(diǎn)struct ListNode* fast = dummy;struct ListNode* slow = dummy;// 快指針先向前移動(dòng)n步for (int i = 0; i < n; i++) {fast = fast->next;}// fast再提前走一步，因?yàn)樾枰宻low指向刪除節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn)fast = fast->next;// 快慢指針同時(shí)移動(dòng)，直到快指針到達(dá)鏈表末尾while (fast) {fast = fast->next;slow = slow->next;}// 刪除慢指針的下一個(gè)節(jié)點(diǎn)（即倒數(shù)第n個(gè)節(jié)點(diǎn)）slow->next = slow->next->next;// 更新頭節(jié)點(diǎn)（dummy是虛擬頭節(jié)點(diǎn)，刪除操作不會(huì)影響head）head = dummy->next;// 釋放虛擬頭節(jié)點(diǎn)的內(nèi)存（注意：這里應(yīng)該釋放dummy，而不是釋放dummy->next，因?yàn)閐ummy->next是實(shí)際的鏈表節(jié)點(diǎn)）free(dummy);// 返回更新后的頭節(jié)點(diǎn)return head;
}

3鏈表相交

給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回?null?。

圖示兩個(gè)鏈表在節(jié)點(diǎn)?c1?開(kāi)始相交：

題目數(shù)據(jù)?保證?整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須?保持其原始結(jié)構(gòu)?。

示例 1：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開(kāi)始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,0,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。

示例?2：

輸入：intersectVal?= 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2'
解釋：相交節(jié)點(diǎn)的值為 2 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開(kāi)始算起，鏈表 A 為 [0,9,1,2,4]，鏈表 B 為 [3,2,4]。
在 A 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 1 個(gè)節(jié)點(diǎn)。

示例?3：

輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
輸出：null
解釋：從各自的表頭開(kāi)始算起，鏈表 A 為 [2,6,4]，鏈表 B 為 [1,5]。
由于這兩個(gè)鏈表不相交，所以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個(gè)鏈表不相交，因此返回 null 。

提示：

• listA?中節(jié)點(diǎn)數(shù)目為?m
• listB?中節(jié)點(diǎn)數(shù)目為?n
• 0 <= m, n <= 3 * 104
• 1 <= Node.val <= 105
• 0 <= skipA <= m
• 0 <= skipB <= n
• 如果?listA?和?listB?沒(méi)有交點(diǎn)，intersectVal?為?0
• 如果?listA?和?listB?有交點(diǎn)，intersectVal == listA[skipA + 1] == listB[skipB + 1]

思路：

1. 初始化變量：定義?longList?和?shortList?用于存儲(chǔ)長(zhǎng)鏈表和短鏈表的頭節(jié)點(diǎn)，lenA?和?lenB?用于存儲(chǔ)兩個(gè)鏈表的長(zhǎng)度，gap?用于存儲(chǔ)長(zhǎng)度差。
2. 計(jì)算鏈表長(zhǎng)度：通過(guò)遍歷鏈表?headA?和?headB，分別計(jì)算它們的長(zhǎng)度?lenA?和?lenB。
3. 確定長(zhǎng)鏈表和短鏈表：通過(guò)比較?lenA?和?lenB，確定哪個(gè)是長(zhǎng)鏈表，哪個(gè)是短鏈表，并計(jì)算長(zhǎng)度差?gap。
4. 尾部對(duì)齊：將長(zhǎng)鏈表?longList?移動(dòng)?gap?步，使得兩個(gè)鏈表的尾部對(duì)齊。
5. 同時(shí)移動(dòng)并檢查交點(diǎn)：同時(shí)移動(dòng)?longList?和?shortList，檢查是否有相同的節(jié)點(diǎn)。如果找到相同的節(jié)點(diǎn)，則返回該節(jié)點(diǎn)（即交點(diǎn)）。
6. 返回結(jié)果：如果沒(méi)有找到交點(diǎn)，則返回?NULL。

代碼：

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {struct ListNode *longList = NULL, *shortList = NULL;int lenA = 0, lenB = 0, gap = 0;// 求出兩個(gè)鏈表的長(zhǎng)度shortList = headA;while (shortList) {lenA++;shortList = shortList->next;}shortList = headB;while (shortList) {lenB++;shortList = shortList->next;}// 確定長(zhǎng)鏈表和短鏈表，并計(jì)算長(zhǎng)度差if (lenA > lenB) {longList = headA;shortList = headB;gap = lenA - lenB;} else {longList = headB;shortList = headA;gap = lenB - lenA;}// 將長(zhǎng)鏈表和短鏈表的尾部對(duì)齊while (gap--) {longList = longList->next;}// 同時(shí)移動(dòng)長(zhǎng)鏈表和短鏈表，檢查是否有相同的節(jié)點(diǎn)while (longList) {if (longList == shortList) return longList; // 找到交點(diǎn)longList = longList->next;shortList = shortList->next;}// 沒(méi)有找到交點(diǎn)return NULL;
}