【第十五天 - Linked list 题目分析】

• 先简单回顾一下，今天预计分析的题目：
• 24. Swap Nodes in Pairs
• 题目连结：https://leetcode.com/problems/swap-nodes-in-pairs/
• 题目叙述：
  

• 昨天问到，若 input 为 [1,2,3] 那麽 output 为 [2,1,3] 还是 [1,3,2] ?

  • 答案是 [2,1,3]，根据题目的需求，从头开始读两个 Node，将此两个 Node 做交换，再读两个Node，并做交换，以此类推

• 我们使用 迭代/递回 来解这个题目

  迭代 Iteration

  • 我们在真正的 Linked list 前，做一个假的 node 作为开头，称为 dummy node，dummy node 後面接的资料，才是真正 input 传进来的 head
  • 所以我们每次执行 while 回圈都要先判断， current 後面两个资料是否都存在
    • 若都存在，我们就将第一个 Node 叫做 first，第二个 Node 叫做 second (这两个点预计要做交换)
    1. first 即将变成第二个点( second )，所以 first 指向的地方，要变成原本 second 指向的位置
    2. second 即将变成第一个点( first )，所以 second 指向的地方，就会变成 first
    3. 然後将 current 指向交换後的第一个位置 ( second )
    4. 经过上面三个步骤，交换完成，所以 current 会跳到 first 的位置，等待下一次再交换

• python 实作迭代如下：

    class Solution:
        def swapPairs(self, head: ListNode) -> ListNode:
    #       先储存一个
            dummy = ListNode(0)
            dummy.next = head
            current = dummy

            while current.next != None and current.next.next != None:
    #           first 跟 second 储存准备交换的 Node
                first = current.next
                second = current.next.next
    #           先把 first Node 指向 second 的下一个Node
                first.next = second.next
    #           先把 second Node 指向 first 的下一个Node 
                second.next = first 
    #           先把 second Node 指向 即将变成第一个点的 second 的下一个Node 
                current.next = second        
    #           把 current 跳到 first 的位置
                current = first
            return dummy.next

递回 Recursive

• 根据题目，假设给定一个 linked list：
  

我们需要输出两两交换位置後的 linked list：

• 透过观察，我们可以发现这个问题可以递回分割成小问题：
  给定一个 node *n，*假设 n 的下下个 node 之後的答案我们都知道了，则我们只要将 n 与 n 的下一个 node 交换位置，再接上後面的答案即可。
• 也就是说长度为 6 的 list，我们只要知道後四个节点的答案，就可以得到全部的答案；而要知道後四个节点的答案，只需要先知道後两个节点的答案，依此类推。
  

利用此递回关系，我们不断将问题化简成较短的 list ，直到 list 长度为 0 或 1 时，我们终於可以知道答案：

• 当 list 长度为 0，则答案为 None
• 当 list 长度为 1，则答案就是当前这个节点。

综合以上发现我们可以列出递回关系式。为了方便表示，此处用一般的 list 进行表示，并且以 node_i+1 表示 node_i 所指向的下一个节点：

其中，前两种 case 为终止条件，第三个 case 为递回关系。

有了递回关系式，我们便可以撰写程序：

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
#       head 指向第一个位置，若为空，则回传 None
				if head is None: return None

#       second 指向第二个位置，若为空，则回传 None        
        second = head.next
        if second is None: return head

#       rest 指向剩下的位置 (就是第二个位置之後)
        rest = second.next
        
#       交换前 [head, second, rest...] -> 交换後 [second, head, rest...]
#       第二个指向第一个，第一个指向剩下的
        second.next = head
        head.next = self.swapPairs(rest)
        
        return second