0024. 两两交换链表中的节点

0024. 两两交换链表中的节点 #

  • 标签:递归、链表
  • 难度:中等

题目大意 #

给定一个链表,按顺序每两个节点交换一下,并返回交换后的链表。要求需要实际进行节点交换,而不是纸改变节点内部的值。

解题思路 #

遍历链表,并判断当前链表后两位节点是否为空。如果后两个节点不为空,则使用三个指针:curr 指向当前节点,node1 指向下一个节点,node2 指向下面第二个节点。

将 curr 指向 node2,node1 指向 node2 后边的节点,node2 指向 node1。则节点关系由 curr → node1 → node2 变为了 curr → node2 → node1。

依次类推,最终返回头节点。

上述我们并判断的是当前链表后两位节点是否为空,可以在一开始的时候新建一个节点 new_head,作为新的头节点加到链表头部,最终返回结果的时候,直接返回 new_head.next 即可。

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
        new_head = ListNode(0)
        new_head.next = head
        curr = new_head
        while curr.next and curr.next.next:
            node1 = curr.next
            node2 = curr.next.next
            curr.next = node2
            node1.next = node2.next
            node2.next = node1
            curr = node1
        return new_head.next
本站总访问量  次  |  您是本站第  位访问者