Problem: 24. 兩兩交換鏈表中的節點
題目：給你一個鏈表，兩兩交換其中相鄰的節點，并返回交換后鏈表的頭節點。你必須在不修改節點內部的值的情況下完成本題（即，只能進行節點交換）。

整體思路

這段代碼旨在解決一個經典的鏈表操作問題：兩兩交換鏈表中的節點 (Swap Nodes in Pairs)。問題要求將鏈表中每兩個相鄰的節點進行交換，并返回交換后的鏈表。例如，1->2->3->4 應變為 2->1->4->3。

該算法采用了一種 迭代 的方法，通過精心設計的指針操作來完成節點的交換。為了簡化邊界情況（特別是頭節點的交換），它也巧妙地運用了 哨兵節點 (Sentinel Node)。

其核心邏輯步驟如下：

1. 初始化：

   • 哨兵節點：創建一個 dummy 節點，其 next 指向原始鏈表的頭節點 head。這使得對第一對節點的交換與其他節點的交換邏輯完全統一。
   • 指針設置：
     • left 指針：初始化為 dummy。這個指針將始終指向待交換的一對節點的前一個節點。它的作用是連接上一組交換好的部分和當前正在交換的部分。
     • right 指針：初始化為 head。這個指針將始終指向待交換的一對節點中的第一個節點。

2. 迭代交換：

   • 算法使用一個 while 循環來遍歷并交換節點對。
   • 循環條件：while (null != right && null != right.next)。這個條件確保了至少還有一對完整的節點（right 和 right.next）可供交換。如果鏈表為空、只有一個節點，或者只剩最后一個節點，循環都不會執行。
   • 在循環內部（核心交換邏輯）：
     • 假設當前結構是 ... -> left -> right -> right.next -> ...。目標是變為 ... -> left -> right.next -> right -> ...。
     • left.next = right.next;：首先，將 left 的 next 指針指向 right 的下一個節點。這是將交換后的新“頭”節點連接到前面的鏈表上。
     • right.next = right.next.next;：接著，將 right 的 next 指針指向它原來下一個節點的下一個節點，即跳過中間的節點。
     • left.next.next = right;：最后，將原來 right.next 的 next 指針指向 right，完成兩個節點的交換。
   • 指針前移：
     • left = right;：完成一對交換后，right 節點現在是這一對中的第二個（在后面）。我們需要為下一輪交換做準備，所以將 left 指針移動到 right 的位置。
     • right = left.next;：將 right 指針移動到下一對節點的第一個節點。

3. 返回結果：

   • 循環結束后，所有節點對都已交換完畢。dummy.next 指向了交換后鏈表的真正頭節點，將其返回。

完整代碼

/*** Definition for singly-linked list.*/
class ListNode {int val;ListNode next;ListNode() {}ListNode(int val) { this.val = val; }ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}class Solution {/*** 兩兩交換鏈表中的節點。* @param head 原始鏈表的頭節點* @return 交換后鏈表的頭節點*/public ListNode swapPairs(ListNode head) {// 創建一個哨兵節點，簡化頭節點交換的邏輯。ListNode dummy = new ListNode(0, head);// left 指針指向待交換對的前一個節點。ListNode left = dummy;// right 指針指向待交換對的第一個節點。ListNode right = head;// 循環條件：確保至少還有一對完整的節點可以交換。while (null != right && null != right.next) {// 核心交換邏輯，可以想象為三步指針重定向：// 假設原始是: left -> n1 -> n2 -> ...// 其中 n1 是 right, n2 是 right.next// 1. left 的 next 指向 n2left.next = right.next;// 2. n1 的 next 指向 n2 原來的 nextright.next = right.next.next;// 3. n2 的 next 指向 n1left.next.next = right;// 交換后，鏈表變為: left -> n2 -> n1 -> ...// 為下一輪交換做準備，移動指針：// left 移動到 n1 的位置left = right;// right 移動到 n1 的下一個位置，即下一對的第一個節點right = left.next;}// 返回哨兵節點的下一個節點，即新鏈表的頭。return dummy.next;}
}

時空復雜度

時間復雜度：O(N)

1. 循環次數：while 循環遍歷整個鏈表。right 指針每次前進兩步（邏輯上）。整個鏈表被掃描了一次。
2. 每次操作：在循環的每一次迭代中，執行的都是常數次（固定次數）的指針賦值操作。

綜合分析：
算法的時間復雜度與鏈表的長度 N 成線性關系。因此，時間復雜度為 O(N)。

空間復雜度：O(1)

1. 主要存儲開銷：算法只創建了 dummy, left, right 等幾個額外的指針變量。
2. 空間大小：這些變量的數量是固定的，與輸入鏈表的長度 N 無關。

綜合分析：
算法沒有使用任何與輸入規模成比例的額外數據結構。因此，其額外輔助空間復雜度為 O(1)。這是一個高效的原地算法。