题目描述
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换)。
示例 1:
输入:head = [1,2,3,4]
输出:[2,1,4,3]
示例 2:
输入:head = []
输出:[]
示例 3:
输入:head = [1]
输出:[1]
提示:
- 链表中节点的数目在范围 [0, 100] 内
- 0 <= Node.val <= 100
思路
需要的留言,挺简单的其实
迭代解法
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:node0 = dummy = ListNode(next=head) node1 = headwhile node1 and node1.next: node2 = node1.nextnode3 = node2.nextnode0.next = node2 node2.next = node1 node1.next = node3 node0 = node1 node1 = node3 return dummy.next
递归解法
class Solution:def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:if head is None or head.next is None: return head node1 = headnode2 = head.nextnode3 = node2.nextnode1.next = self.swapPairs(node3) node2.next = node1 return node2