【算法日常】鏈表節點兩兩交換

鏈表節點兩兩交換

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/swap-nodes-in-pairs

給定一個鏈表，兩兩交換其中相鄰的節點，并返回交換后的鏈表。

你不能只是單純的改變節點內部的值，而是需要實際的進行節點交換。

示例:
給定 1->2->3->4, 你應該返回 2->1->4->3.

本題考慮到量個兩種解法：第一種用循環的方法去解答，第二種用遞歸的方式去解答，但是遞歸在前面的介紹說過，遞歸并不是最好的解法，相反遞歸還可能存在遞歸棧溢出的問題，而且遞歸比循環更加的耗費資源。這里是記錄一下若用遞歸的解答方式該怎解答。

第一種解法 循環

循環方式解答，申請一個新的節點pre，將新的節點的next指向鏈表的開始部位。在使用一個tmp指針變量指向“需要交換的第一個節點”前面的節點。（第一組需要交換的節點的前一個節點當然是pre）
在使用start和end兩個指針分別指向需要交換的第一個和第二個節點。
進行交換，將“本組需要交換的節點”的 前一個節點 的next指針指向“需要交換的第二個節點”
其次將 “本組需要交換的第一個節點”的next指針指向 “本組需要交換的第二個節點”的后面的那個節點
然后將 “本組需要交換的第二個節點”的next指針指向 "本組需要交換的第一個節點", 本次交換結束
最后將tmp的挪到下一組“需要交換的節點”的前一個節點，（即本次交換完成后的start節點）
當然交換過程可以用比較簡潔的一行賦值語句進行，這里把他分開的原因是更清晰的展現交換的過程
時間復雜度 O(n), 空間復雜度 O(1)

代碼如下：

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-12
# @File     : swap_pairs_linked.py
# Software  : study

"""
兩兩交換鏈表節點
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def swap_pairs(head: ListNode) -> ListNode:
    pre = ListNode(0)
    pre.next = head
    tmp = pre
        start = tmp.next  # “需要交換的第一個節點”
        end = tmp.next.next  # “需要交換的第二個節點”

        while tmp.next and tmp.next.next:
        tmp.next = end    # “需要交換的第一個節點”的前面的一個節點，指向需要交換的第二個節點
        start.next = end.next  # “需要交換的第一個節點”指向“需要交換的第二個節點”的后面的節點
        end.next = start   # “需要交換的第二個節點”指向“需要交換的第一個節點”
        # 上面交換完畢，現在start節點處于第二個節點的位置， end節點在第一個節點的位置
        tmp = start  # 將tmp指向下一組“需要交換的第一個節點”的前面的一個節點， 即本次交換完成的第二個節點的位置

    return pre.next

if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    result = swap_pairs(node1)

    while result:
        print(result.val)
        result = result.next

輸出結果:

2
1
4
3
5

第二種解法 遞歸

遞歸解法，是將多組的交換抽象成一組交換，是先找到“本組需要交換的節點”的下一個節點
進行交換，“本組需要交換的第一個節點”的next指針指向“本組需要交換的第二個節點”的下一個節點
其次將“本組需要交換的第二個節點”的next指針指向 “本組需要交換的第一個節點”， 然后返回交換后的第一個節點（即交換前的第二個節點）

代碼如下：

# -*- coding: utf-8 -*-
# @Author   : xaohuihui
# @Time     : 19-12-12
# @File     : swap_pairs_linked.py
# Software  : study

"""
兩兩交換鏈表節點
"""

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None

def swap_pairs(head: ListNode) -> ListNode:
    if head is None or head.next is None:   # 當長度為奇數時返回最后一個節點，當長度為偶數的時候返回None
        print(head.val if head else head)
        return head

    pre = head.next  # head 為“第一個需要交換節點”， pre 為“第二個需要交換的節點”
    print(head.val, pre.val)
    head.next = swap_pairs(pre.next)  # “第一個需要交換的節點” 指向 “第二個需要交換的節點”的后面的節點
    pre.next = head  # “第二個需要交換的節點” 指向 “第一個需要交換的節點”
    print("swap", head.val, pre.val, head.next.val if head.next else head.next)
    return pre

if __name__ == '__main__':
    node1 = ListNode(1)
    node2 = ListNode(2)
    node3 = ListNode(3)
    node4 = ListNode(4)
    node5 = ListNode(5)

    node1.next = node2
    node2.next = node3
    node3.next = node4
    node4.next = node5

    result = swap_pairs(node1)

    while result:
        print(result.val)
        result = result.next

輸出結果：

1 2
3 4
5
swap 3 4 5
swap 1 2 4
2
1
4
3
5