# 0024. 兩兩交換鏈表中的節點 ## 題目地址(24. 兩兩交換鏈表中的節點) <https://leetcode-cn.com/problems/swap-nodes-in-pairs/> ## 題目描述 給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。 你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。  ``` <pre class="calibre18">``` 示例 1： 輸入：head = [1,2,3,4] 輸出：[2,1,4,3] 示例 2： 輸入：head = [] 輸出：[] 示例 3： 輸入：head = [1] 輸出：[1] 提示： 鏈表中節點的數目在范圍 [0, 100] 內 0 <= Node.val <= 100 ``` ``` ## 前置知識 - 鏈表 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路 設置一個 dummy 節點簡化操作，dummy next 指向 head。 1. 初始化 first 為第一個節點 2. 初始化 second 為第二個節點 3. 初始化 current 為 dummy 4. first.next = second.next 5. second.next = first 6. current.next = second 7. current 移動兩格 8. 重復  （圖片來自： <https://github.com/MisterBooo/LeetCodeAnimation>) ## 關鍵點解析 1. 鏈表這種數據結構的特點和使用 2. dummyHead 簡化操作 ## 代碼 - 語言支持：JS，Python3 ``` <pre class="calibre18">``` <span class="hljs-title">/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */</span> <span class="hljs-title">/** * @param {ListNode} head * @return {ListNode} */</span> <span class="hljs-keyword">var</span> swapPairs = <span class="hljs-function"><span class="hljs-keyword">function</span>(<span class="hljs-params">head</span>) </span>{ <span class="hljs-keyword">const</span> dummy = <span class="hljs-keyword">new</span> ListNode(<span class="hljs-params">0</span>); dummy.next = head; <span class="hljs-keyword">let</span> current = dummy; <span class="hljs-keyword">while</span> (current.next != <span class="hljs-params">null</span> && current.next.next != <span class="hljs-params">null</span>) { <span class="hljs-title">// 初始化雙指針</span> <span class="hljs-keyword">const</span> first = current.next; <span class="hljs-keyword">const</span> second = current.next.next; <span class="hljs-title">// 更新雙指針和 current 指針</span> first.next = second.next; second.next = first; current.next = second; <span class="hljs-title">// 更新指針</span> current = current.next.next; } <span class="hljs-keyword">return</span> dummy.next; }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span> <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">swapPairs</span><span class="hljs-params">(self, head: ListNode)</span> -> ListNode:</span> <span class="hljs-string">""" 用遞歸實現鏈表相鄰互換： 第一個節點的 next 是第三、第四個節點交換的結果，第二個節點的 next 是第一個節點； 第三個節點的 next 是第五、第六個節點交換的結果，第四個節點的 next 是第三個節點； 以此類推 :param ListNode head :return ListNode """</span> <span class="hljs-title"># 如果為 None 或 next 為 None，則直接返回</span> <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> head <span class="hljs-keyword">or</span> <span class="hljs-keyword">not</span> head.next: <span class="hljs-keyword">return</span> head _next = head.next head.next = self.swapPairs(_next.next) _next.next = head <span class="hljs-keyword">return</span> _next ``` ``` **復雜度分析** - 時間復雜度：O(N)O(N)O(N) - 空間復雜度：O(1)O(1)O(1) 大家對此有何看法，歡迎給我留言，我有時間都會一一查看回答。更多算法套路可以訪問我的 LeetCode 題解倉庫：<https://github.com/azl397985856/leetcode> 。 目前已經 37K star 啦。 大家也可以關注我的公眾號《力扣加加》帶你啃下算法這塊硬骨頭。