143. 重排链表

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

给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

示例 1:

给定链表 1->2->3->4, 重新排列为 1->4->2->3.

示例 2:

给定链表 1->2->3->4->5, 重新排列为 1->5->2->4->3.

通过次数29,401 | 提交次数52,486

Third Try

2020-10-20

每日一提，刚好练手。一开始想要不截断，直接倒排然后合并，后来发现内存引用其实是同一个链表。于是只能继续从中点截断，然后倒排合并。中点截断用的是快慢节点的方法，细节部分列出奇数和偶数的情况也就知道了。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: ListNode) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        if not head:
            return head 
            
        # split in the middle, reverse; 
        # 1 2 3 4 --> 1,2 -> 2, 4 -> 2.next 
        # 1 2 3 4 5 -> 1,2 -> 2, 4 -> 3, None -> 3.next 
        node = head 
        prenode = head.next 
        while prenode and prenode.next:
            node = node.next 
            prenode = prenode.next.next
        mnode = node.next
        node.next = None            

        # reverse the chain
        rhead = None  
        while mnode:
            node = mnode 
            mnode = mnode.next 
            node.next = rhead 
            rhead = node 
        
        # 一开始是没有考虑拆分的，以为直接变成两条链表，这样需要考虑奇数和偶数的情况
        # 但是由于需要保留原来的节点，除非复制一份，否则没法实现两条链表一条正序一条反序
        # even vs odd 
        # 1 2 3 4 
        # 4 3 2 1 
        # 1 2 3 4 5
        # 5 4 3 2 1 
        dummyHead = tail = ListNode(None)            
        while head and rhead:
            ni = head
            nr = rhead 
            head = head.next 
            rhead = rhead.next  
            ni.next = None 
            nr.next = None
            tail.next = ni 
            ni.next = nr 
            tail = nr 

        if head:
            tail.next = head 
        if rhead:
            tail.next = rhead 

        return dummyHead.next  
            
             

执行用时：88 ms, 在所有 Python3 提交中击败了99.50%的用户
内存消耗：22.7 MB, 在所有 Python3 提交中击败了16.58%

Second Try

2020-07-09

First Try中在链表场合使用列表总觉得有点作弊，不使用列表的话，那就是倒排，然后两个链表合并.

对于快慢指针真是越来越熟练了，多画几个偶数和奇数长度的列表模拟下就知道了。

reverse递归倒排链表，虽然之前写过一次，现在再写还是迟滞了一会儿。还是没有先找到尾部然后迭代插入的写法来得容易理解。

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        # 不使用列表的话，那就是倒排，然后两个链表合并
        if not head:
            return head 
            
        slow = head 
        fast = head.next 

        while fast and fast.next:
            slow = slow.next 
            fast = fast.next.next 
        right_part = slow.next 
        slow.next = None 
        # print("middle", slow.val)
        def reverse(head):
            if not (head and head.next):
                return head 
            last = reverse(head.next)
            head.next.next = head 
            head.next = None 
            return last 
        
        right_part = reverse(right_part)
        # print('right part', right_part.val)
        dummy = node = ListNode(None)
        while head and right_part:
            node.next = head
            head = head.next  
            node.next.next = right_part
            right_part = right_part.next 
            node = node.next.next
            node.next = None # 各种尾大不掉需要去考虑
        node.next = head if head else right_part
        return dummy.next 

执行用时：92 ms, 在所有 Python 提交中击败了60.00%的用户
内存消耗：45.8 MB, 在所有 Python 提交中击败了50.00%的用户

First Try

2020-07-07

空间暴力法，不知道是否有O(1)空间的写法。。。

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: None Do not return anything, modify head in-place instead.
        """
        if not head:
            return head 
        node = head 
        cache = []
        while node:
            cache.append(node)
            node = node.next 
        n = len(cache)
        for left in range(0, n):
            right = n - 1 - left  #这个写法比较无脑，不用管left到n/2的地方结束的奇偶情况
            if left == right:
                cache[left].next = None # 不然就陷入无限循环
                break 
            elif left + 1 == right:
                cache[left].next = cache[right] 
                cache[right].next = None # 不然就陷入循环中
                break
            else:
                cache[left].next = cache[right] 
                cache[right].next = cache[left + 1]

        return cache[0]

执行用时：76 ms, 在所有 Python 提交中击败了94.04%的用户
内存消耗：33.8 MB, 在所有 Python 提交中击败了50.00%的用户

143. 重排链表​

Third Try​

Second Try​

First Try​

143. 重排链表

Third Try

Second Try

First Try