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

难度中等827

给定一个链表,两两交换其中相邻的节点,并返回交换后的链表。

你不能只是单纯的改变节点内部的值,而是需要实际的进行节点交换。

示例 1:

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

示例 2:

1
2
输入:head = []
输出:[]

示例 3:

1
2
输入:head = [1]
输出:[1]

提示:

  • 链表中节点的数目在范围 [0, 100]
  • 0 <= Node.val <= 100

进阶:你能在不修改链表节点值的情况下解决这个问题吗?(也就是说,仅修改节点本身。)

  1. 迭代解法:开了一个虚拟节点,然后pid的next是将要交换的第一个节点,pid.next.next是第二个

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    # Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
    temphead=ListNode(0)
    temphead.next=head
    pid=temphead
    while pid.next and pid.next.next:
    node1=pid.next
    node2=pid.next.next

    pid.next=node2
    node1.next=node2.next
    node2.next=node1
    pid=node2.next
    return temphead.next
  2. 递归解法:见里面的注释

    首先思考递归终止条件,然后思考里面的递归过程

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    # Definition for singly-linked list.
    # class ListNode:
    # def __init__(self, val=0, next=None):
    # self.val = val
    # self.next = next
    class Solution:
    def swapPairs(self, head: ListNode) -> ListNode:
    # 终止条件:head是空或者head.next是空 比如[],[1]
    if not head or not head.next:
    return head

    #1,2,3,4
    temp=head.next #因为马上要修改
    #1->2->3->4
    #修改好了4->3
    #所以1->4->3
    head.next=self.swapPairs(temp.next)
    #temp相当于2,2->1
    temp.next=head
    return temp