递归类
LeeCode 24.两两交换链表中的节点
题目描述
题目链接:https://leetcode.cn/problems/swap-nodes-in-pairs/description/
给你一个链表,两两交换其中相邻的节点,并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题(即,只能进行节点交换):
输入:head = [1,2,3,4]
输出:[2,1,4,3]
解题思路
迭代解法
- 创建哨兵节点dummy,表示节点0
- 将node0指向node2
- 将node2.指向node1
- 将node1指向node3
- 更新node0为node1,更新node1为node3
- 如果node1和node1.next都不为空,就回到第2步,进行下一轮交换
- 返回dummy.next,作为新链表的头节点
复杂度分析
- 时间复杂度:O(n)
- 空间复杂度:O(1)
示例代码
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
node0 = dummy = ListNode(next=head) # 用哨兵节点简化代码逻辑
node1 = head
while node1 and node1.next: # 至少有两个节点
node2 = node1.next
node3 = node2.next
node0.next = node2 # 0 -> 2
node2.next = node1 # 2 -> 1
node1.next = node3 # 1 -> 3
node0 = node1 # 下一轮交换,0 是 1
node1 = node3 # 下一轮交换,1 是 3
return dummy.next # 返回新链表的头节点
递归解法
将方法一改造为递归解法,则:
- 递归边界(终止条件):链表中没有节点或链表只有一个节点,此时无法再进行交换
- 用head表示原始链表头节点,新链表第二个节点,用newhead表示新链表头节点,原始链表第二个节点
- 将其余节点两两交换,即:head.next=swapPairs(newhead.next)
- 交换后的头节点为head的下一个节点
- 返回新链表的头节点newhead
复杂度分析
- 时间复杂度:O(n),其中n是链表的节点数量。需要对每个节点进行更新指针的操作
- 空间复杂度:O(n),其中n是链表的节点数量。空间复杂度主要取决于递归调用的栈空间
示例代码
class Solution:
def swapPairs(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
newHead = head.next
head.next = self.swapPairs(newHead.next)
newHead.next = head
return newHead
Comments NOTHING