Python编程题49--两两交换链表中的节点
2022/1/30 17:04:37
本文主要是介绍Python编程题49--两两交换链表中的节点,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目
给定一个链表,请在不修改节点内部值的情况下,两两交换其中相邻的节点,并返回交换后链表的头节点。
例如:
原链表转换为列表:[1, 2, 3, 4]
最终的链表转换为列表:[2, 1, 4, 3]原链表转换为列表:[1, 2, 3, 4, 5]
最终的链表转换为列表:[2, 1, 4, 3, 5]原链表转换为列表:[]
最终的链表转换为列表:[]
已知 链表节点的定义、链表与列表相互转换 的代码如下:
class ListNode: # 单链表 def __init__(self, val=0, next=None): self.val = val # 链表节点上存储的元素 self.next = next # 指向下一个链表节点 def list_to_list_node(numbers): # 将列表转换为单向链表,并返回链表的头节点 dummy_head = ListNode(0) pre = dummy_head for number in numbers: pre.next = ListNode(number) pre = pre.next pre = dummy_head.next return pre def list_node_to_list(node): # 将单向链表转换为列表 result = [] while node: result.append(node.val) node = node.next return result
实现思路
- 假设初始链表节点如下:节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5,设置一个虚拟头节点后,链表变为:虚拟头节点 -> 节点1 -> 节点2 -> 节点3 -> 节点4 -> 节点5
- 首先,需用3个变量保存在除虚拟头节点外的前3个节点,因为等会需要改变节点的指向
- 第一步,让当前节点通过 next 指向节点2
- 第二步,让当前节点的下个节点通过 next 指向节点1
- 第三步,让当前节点的下下个节点通过 next 指向节点3
- 第四步,让当前节点移动2位,也就是到 节点1 的位置,以便继续交换后面的节点
- 通过上面几步处理后,链表变为:虚拟头节点 -> 节点2 -> 节点1 -> 节点3 -> 节点4 -> 节点5,同时当前节点已经变为 节点1
- 循环以上几步操作,直到当前节点的下个节点或下下个节点出现空时,说明节点交换完成,最终得到的链表为:虚拟头节点 -> 节点2 -> 节点1 -> 节点4 -> 节点3 -> 节点5
- 最后,将链表虚拟头节点的下一个节点,也就是将 节点2 返回即可
代码实现--迭代
class Solution: def swapPairs(self, head: ListNode) -> ListNode: dummy_head = ListNode(next=head) # 设置虚拟头节点 cur = dummy_head while cur.next is not None and cur.next.next is not None: tmp1, tmp2, tmp3 = cur.next, cur.next.next, cur.next.next.next # 临时节点1、节点2、节点3 cur.next = tmp2 # 改变节点指向,当前节点通过 next 指向节点2 cur.next.next = tmp1 # 改变节点指向,下个节点通过 next 指向节点1 cur.next.next.next = tmp3 # 改变节点指向,下下个节点通过 next 指向节点3 cur = cur.next.next # 当前节点移动2位(变为节点1) return dummy_head.next
代码实现--递归
class Solution: def swapPairs(self, head: ListNode) -> ListNode: cur = head while cur is None or cur.next is None: # 递归终止条件:当前节点或下个节点为空 return cur post = cur.next # 临时保存下个节点 cur.next = self.swapPairs(post.next) # 改变节点指向,当前节点通过 next 指向经过递归处理的子链表 post.next = cur # 改变节点指向,下个节点通过 next 指向当前节点 return post # 每次递归调用后,当前节点和下个节点指向发生改变,子链表都是从下个节点开始
更多Python编程题,等你来挑战:Python编程题汇总(持续更新中……)
这篇关于Python编程题49--两两交换链表中的节点的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04Python外包有哪些常见的主要库-icode9专业技术文章分享
- 2024-10-02基于深度学习的钢铁缺陷检测系统(yolov8、注意力机制、PyQt5界面、Python)
- 2024-10-01怎么用python搭建一个系统-icode9专业技术文章分享
- 2024-09-30Python基础入门教程
- 2024-09-30获取参数学习:Python中的基础教程
- 2024-09-30Python编程基础详解
- 2024-09-29点击加载学习:Python编程基础教程
- 2024-09-29数据科学五大Python前端库:第二部分
- 2024-09-27使用python 将ETH账户的资产打散
- 2024-09-26Python编程基础