做电影网站程序好用吗,做淘宝代码的网站,搭建网站,90设计网站如何接单题目名称#xff1a; 重排链表
链接#xff1a; . - 力扣#xff08;LeetCode#xff09;
介绍#xff1a;本题的目标是将链表进行重新组合#xff0c;如下图。 如果按照标准的解法#xff0c;我们需要实现三步
1. 链表中点的获取
2. 链表的反转
3. 链…题目名称 重排链表
链接 . - 力扣LeetCode
介绍本题的目标是将链表进行重新组合如下图。 如果按照标准的解法我们需要实现三步
1. 链表中点的获取
2. 链表的反转
3. 链表的插入
而每一步都是比较经典的链表操作。
首先为了获取链表中点我们可以通过快慢链表。
def getMidNode(head: ListNode)-ListNode:fast_node headslow_node headwhile(fast_node.next.next and slow_node.next):fast_node fast_node.next.nextslow_node slow_node.nextreturn slow_node
然后我们需要进行链表的反转。
def reverseList(head: ListNode)-ListNode:prev_node Nonecur_node headwhile(cur_node):next_node cur_node.nextcur_node.next prev_nodeprev_node cur_nodecur_node next_nodereturn prev_node
其中需要注意的是我们要存储prev_node next_node; 在while循环中我们每次需要判断cur_node, 但是更重要的是在最后一次cur_node必然为空因此最后需要返回的是prev_node. 最后我们需要实现列表的融合。
对应的就是 A-- B 和 C-- D 变为 A--C -- B -- D . 为了实现这一操作 我们每次需要对于两个链表的next node进行备份然后再更改current node的相互关系然后再去处理next node。
def mergeLists(headA:ListNode, headB:ListNode):curA headAcurB headBwhile(curA and curB):tmpA curA.nexttmpB curB.nextcurA.next curBcurB.next tmpAcurA tmpAcurB tmpBreturn headA
实现了这些子模块后我们经过整合就可以实现最后的功能。为了把两个链表进行拆分我们需要将中间节点的next在备份之后设定为0。
midNode getMidNode(head)headA headheadB midNode.nextmidNode.next NoneheadB reverseList(headB)result mergeLists(headA, headB)return result
