# 24. Swap Nodes in Pairs
###### tags: `鏈結串列` `遞迴`

https://leetcode.com/problems/swap-nodes-in-pairs/

[toc]

# 思路
1. 題目要看好，題目好像允許交換val ?
2. swap 可以使用，這樣就不用maintain 一個tem

            pre.val,cur.val=cur.val,pre.val
            
            #tem=pre.val 
            #pre.val =cur.val 
            #cur.val=tem 
            

3. 因為原本list就是連接的，所以遇到沒辦法換的，就直接break就好。
4. 邊際值要練系，例如如果head 和head.next都沒有怎麼辦，直接回傳head ，還有第三點說的，最尾端怎麼辦。
6.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        
        if not head or not head.next :
            return head 
        
        pre=head 
        cur=head.next 
        
        while pre and cur: 
            tem=pre.val 
            pre.val =cur.val 
            cur.val=tem 
            
            # 本來list 都是連接的，所以直接break 就好
            if  not cur.next or not cur.next.next : 
                break 
            pre=cur.next 
            cur=cur.next.next
        
        return head 
        

# 方法 ②：遞迴
稍微拆解一下題目，其實題目要做的事情是以兩個點為一組，完成以下操作：

將第一個點（head）指向第三個點（head.next.next）
將第二個點（head.next）指向第一個點（head）
可能會出類似以下的樣子：

head.next = head.next.next
head.next.next = head

但這樣寫可能會造成第二個點（head.next）被改寫，而失去原本的期待，因此需要先暫存第二的點：

next = head.next
head.next = next.next
next.next = head

以上這樣完成了一組的操作，為了讓所有點都可以依照此規則，可以加入遞迴的方法迭代：

next = head.next
head.next = swapPairs(next.next)
next.next = head

實作

class Solution:
    def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if not head or not head.next: return head
        next = head.next # next 指向第二個點
        head.next = self.swapPairs(next.next) # head 指向第三個點
        next.next = head # next.next 指向第一個點
        return next