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