题目
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。 输入：head = [1,2,3,4] 输出：[2,1,4,3]
解法分析
可以使用虚拟头节点或者递归写法
Python写法
使用虚拟头节点
# 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: Optional[ListNode]) -> Optional[ListNode]:
# 设置一个虚拟头节点
dummy_head = ListNode(next = head)
current = dummy_head
while current.next and current.next.next:
# 保存临时节点
temp1 = current.next
temp2 = current.next.next.next
current.next = current.next.next
current.next.next = temp1
current.next.next.next = temp2
current = current.next.next
return dummy_head.next
使用递归
# 创建单向链表
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
# 递归解法
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if head is None or head.next is None:
return head
# 待翻转的两个node分别是pre和cur
pre = head
cur = head.next
next = head.next.next
cur.next = pre # 交换
pre.next = self.swapPairs(next) # 将以next为head的后续链表两两交换
return cur
