本文為Python算法題集之一的代碼示例

題24：兩兩交換鏈表中的節(jié)點

1. 示例說明

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

  示例 1：

  

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

  示例 2：

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

  示例 3：

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

  提示：

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

---

2. 題目解析

- 題意分解

1. 本題為兩兩交換鏈表中間的節(jié)點
2. 本題的主要計算是2塊，1是鏈表遍歷，2是節(jié)點鏈接調整
3. 基本的解法是單層循環(huán)，鏈表1讀一遍，過程中執(zhí)行節(jié)點鏈接調整，所以基本的時間算法復雜度為O(m）

- 優(yōu)化思路

1. 通常優(yōu)化：減少循環(huán)層次

2. 通常優(yōu)化：增加分支，減少計算集

3. 通常優(yōu)化：采用內置算法來提升計算速度

4. 分析題目特點，分析最優(yōu)解

   1. 標準方法是一次循環(huán)，4個節(jié)點中，第2個節(jié)點鏈接第1個，第1個節(jié)點連接第3個或者第4個【如果第4個存在】

   2. 可以用列表結構進行節(jié)點調整，列表結構簡單，方便維護

   3. 可以用三指針方式一次循環(huán)完成

   4. 此問題可以用嵌套思路，使用遞歸法

---

- 測量工具

• 本地化測試說明：LeetCode網站測試運行時數(shù)據波動很大，因此需要本地化測試解決這個問題
• CheckFuncPerf（本地化函數(shù)用時和內存占用測試模塊）已上傳到CSDN，地址：Python算法題集_檢測函數(shù)用時和內存占用的模塊
• 本題很難超時，本地化超時測試用例自己生成，詳見【最優(yōu)算法章節(jié)】

---

3. 代碼展開

1) 標準求解【四節(jié)點法】

一次遍歷檢查4個節(jié)點，完成節(jié)點鏈接調整

出類拔萃，超過85%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef swapPairs_base(head):if not head:return headif not head.next:return headtmpNode1, tmpNode2 = head, head.nexthead = tmpNode2while tmpNode1 and tmpNode2:tmpNode11 = tmpNode2.nexttmpNode12 = NonetmpNode1.next = tmpNode2.nexttmpNode2.next = tmpNode1if tmpNode11:tmpNode12 = tmpNode11.nextif tmpNode12:tmpNode1.next = tmpNode12tmpNode1 = tmpNode11tmpNode2 = tmpNode12return headresult = cfp.getTimeMemoryStr(Solution.swapPairs_base, ahead)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result'].val))# 運行結果
函數(shù) swapPairs_base 的運行時間為 18.01 ms；內存使用量為 4.00 KB 執(zhí)行結果 = 1

2) 改進版一【列表操作】

將鏈表轉換為數(shù)組，再完成節(jié)點鏈接調整

馬馬虎虎，超過69%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef swapPairs_ext1(head):if not head:return headif not head.next:return headlist_node = []while head:list_node.append(head)head = head.nextiLen = len(list_node)for iIdx in range(len(list_node) // 2):if iIdx * 2 + 2 > iLen:continuelist_node[iIdx*2+1].next = list_node[iIdx*2]if iIdx * 2 + 3 > iLen:list_node[iIdx * 2].next = Noneelif iIdx * 2 + 4 > iLen:list_node[iIdx * 2].next = list_node[iIdx * 2 + 2]else:list_node[iIdx * 2].next = list_node[iIdx * 2 + 3]return list_node[1]result = cfp.getTimeMemoryStr(Solution.swapPairs_ext1, ahead)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result'].val))# 運行結果
函數(shù) swapPairs_ext1 的運行時間為 109.04 ms；內存使用量為 76.00 KB 執(zhí)行結果 = 1

3) 改進版二【三指針法】

使用三指針結構遍歷鏈表，完成節(jié)點鏈接調整

出類拔萃，超過85%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef swapPairs_ext2(head):dummyhead = ListNode(0)dummyhead.next = headnodepre = dummyheadnodeslow = dummyhead.nextif not nodeslow:return dummyhead.nextnodefast = nodeslow.nextwhile nodefast:nodeslow.next = nodefast.nextnodefast.next = nodeslownodepre.next = nodefastnodepre = nodeslownodeslow = nodeslow.nextif not nodeslow:breaknodefast = nodeslow.nextreturn dummyhead.nextresult = cfp.getTimeMemoryStr(Solution.swapPairs_ext2, ahead)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result'].val))# 運行結果
函數(shù) swapPairs_ext2 的運行時間為 17.00 ms；內存使用量為 0.00 KB 執(zhí)行結果 = 1

4) 改進版三【遞歸大法】

采用遞歸方式遍歷鏈表，完成節(jié)點鏈接調整

出神入化，超過96%

import CheckFuncPerf as cfpclass Solution:@staticmethoddef swapPairs_ext3(head):def swapnodepair(head):nodeleft = headif not nodeleft:return headnoderight = nodeleft.nextif not noderight:return headnodeleft.next = swapnodepair(noderight.next)noderight.next = nodeleftreturn noderightreturn swapnodepair(head)result = cfp.getTimeMemoryStr(Solution.swapPairs_ext3, ahead)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result'].val))# 運行結果
Traceback (most recent call last):......
[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded

---

4. 最優(yōu)算法

根據本地日志分析，最優(yōu)算法為第3種swapPairs_ext2

nums = [ x for x in range(200000)]
def generateOneLinkedList(data):head = ListNode()current_node = headfor num in data:new_node = ListNode(num)current_node.next = new_nodecurrent_node = new_nodereturn head.next
ahead = generateOneLinkedList(nums)
result = cfp.getTimeMemoryStr(Solution.swapPairs_base, ahead)
print(result['msg'], '執(zhí)行結果 = {}'.format(result['result'].val))# 算法本地速度實測比較
函數(shù) swapPairs_base 的運行時間為 18.01 ms；內存使用量為 4.00 KB 執(zhí)行結果 = 1
函數(shù) swapPairs_ext1 的運行時間為 109.04 ms；內存使用量為 76.00 KB 執(zhí)行結果 = 1
函數(shù) swapPairs_ext2 的運行時間為 17.00 ms；內存使用量為 0.00 KB 執(zhí)行結果 = 1
Traceback (most recent call last):    # 遞歸法swapPairs_ext3超時......[Previous line repeated 991 more times]
RecursionError: maximum recursion depth exceeded

一日練，一日功，一日不練十日空

may the odds be ever in your favor ~