[Leetcode]24: Swap Nodes in Pairs

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

Problem :
Given a linked list, swap every two adjacent nodes and return its head. You must solve the problem without modifying the values in the list’s nodes (i.e., only nodes themselves may be changed.)

給一個Linklist，把相鄰的node進行交換
Note : 不能修改 Node上的Value

圖來自leetcode

Thoughts :
0. 準備一個prev，接上linklist，整個linklist變成 prev->1->2->3->4
1. 2指給1
2. 1指給3，整個linklist變成 prev->2->1->3->4
3. 開始更新指標，prev指標更新給1，head指標更新給3，開始下一輪更新

Solution :

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        while not head or not head.next:
            return head
        prev = ListNode(0)
        reprev= prev
        while head and head.next:
            #先set up好三個指標curr,secnode,nextswap
            curr = head
            secnode = head.next
            nextswap = head.next.next
            #把2的下一個指給1，1的下一個指給3
            secnode.next = curr
            curr.next = nextswap
            #更新指標
            prev.next = secnode
            prev = curr
            head = nextswap
        return reprev.next

Solution : (Recursive)

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        if head and head.next:
            #找到head的next
            tmp = head.next
            #把1->2跟3->4接起來
            head.next = self.swapPairs(tmp.next)
            #交換
            tmp.next = head
            return tmp
        return head

#time complexity, space complexity