143. 重排链表

https://leetcode-cn.com/problems/reorder-list/

解法一：双端队列

from collections import deque
class Solution:
    def reorderList(self, head: 'ListNode') -> 'None':
        """
        Do not return anything, modify head in-place instead.
        """
        p = head
        d = deque()
        lens = 0
        #所有结点按序放入双端队列
        while p:
            d.append(p)
            p = p.next
            lens += 1
        work = ListNode(None)  #工作节点
        #左边出一个，右边出一个，按此顺序依次连入新链
        for i in range(lens):
            if i%2 == 0:
                tmp = d.popleft()  #弹出队列左边元素
            else:
                tmp = d.pop()  #右边
            work.next = tmp
            work = work.next
        work.next = None  #防止环链

解法二：

从中间切两半，前一半为链1，后一半反转（用头插法）得链2，然后在新链上交替取链1，链2各一个结点即可

class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        Head = ListNode(None)
        Head.next = head
        slow = fast = Head
        while fast.next and fast.next.next:     #快慢指针找中点
            fast = fast.next.next
            slow = slow.next
        #截断
        if fast.next:   #链长为奇，slow指向最中间的结点
            slow = slow.next
        cut = slow.next
        slow.next = None
        
        newHead = ListNode(None)   #新链头
        while cut:  #头插法插入新链
            tmp = cut
            cut = cut.next
            tmp.next = newHead.next
            newHead.next = tmp
        i, j = head, newHead
 
        #两链合并
        Head = ListNode(None)  
        work, i, j = Head, head, newHead.next   #i，j分别为两个链的工作指针
        while i and j:
            #先插一个i到新链
            work.next = i
            work = work.next
            i = i.next
            #再插一个j
            work.next = j
            work = work.next
            j = j.next
        if i:   #若i还有剩，只剩一个
            work.next = i
            work = work.next
        work.next = None    #封尾