【算法日常】链表节点两两交换

链表节点两两交换

题目来源：力扣（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