数据结构与算法1： 链表

题目名称： 重排链表

链接： ​​​​​​. - 力扣（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