Python实现两两交换链表中的节点_假设给定一个链表,请你设计一个程序实现两两交换

题目描述

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。
你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

Leetcode原题地址:https://leetcode-cn.com/problems/swap-nodes-in-pairs/

测试用例

• 示例1
  

输入：head = [1,2,3,4]
输出：[2,1,4,3]

• 示例2

输入：head = []
输出：[]

• 示例3

输入：head = [1]
输出：[1]

代码实现

• 遍历链表

我们需要两两交换链表的节点，很容易就能想到直接遍历链表然后交换链表的节点即可，思路如下：

1. 我们需要交换链表head，head=node1->node2->node3->node4
2. 在交换之前我们需要先保存node1和node2
3. 然后将temp.next=node2
4. 改变node2指向的节点，此时node2应该指向node1，而且node1应该指向node3，所以先改变node1的指向的节点，然后再改变node2指向的节点

class ListNode:
    def __init__(self,val,next=None):
        if isinstance(val,int):
            self.val = val
            self.next = next
        elif isinstance(val,list):
            self.val = val[0]
            self.next = None
            head = self
            for i in range(1,len(val)):
                node = ListNode(val[i])
                head.next = node
                head = head.next

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:

        #定义哑节点
        dummy = ListNode(-1)
        dummy.next = head

        #定义一个临时节点,用来保存交换的状态
        temp = dummy

        #遍历链表
        #注意第一个节点是哑结点,所以我们从第二个开始遍历
        while temp.next and temp.next.next:

            #保存链表相邻的两个节点
            node1 = temp.next
            node2 = temp.next.next

            #将后面的节点移到前面来
            temp.next = node2
            #更改交换后节点的指向
            node1.next = node2.next
            node2.next = node1

            #继续交换后面两个相邻的节点
            temp = node1

        return dummy.next


head = [1,2,3,4]

listnode = ListNode(head)

solution = Solution()
res = solution.swapPairs(listnode)

while res:
    print(res.val)
    res = res.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

• 递归实现

class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        #如果链表的节点个数小于2,不用交换节点直接返回
        if not head or not head.next:
            return head
        #保存链表的下一个节点
        new_head = head.next
        #交换后面的节点
        head.next = self.swapPairs(new_head.next)
        #更新节点的指向
        new_head.next = head
        return new_head
1
2
3
4
5
6
7
8
9
10
11
12

参考：两两交换链表中的节点