0143._reorder_list.md

143. Reorder List

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/reorder-list/description/

内容描述

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You may not modify the values in the list's nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.
Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

找到后半段反转后，再merge

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if not head or not head.next or not head.next.next:
            return
        
        # calculate the length
        n = 0
        dummy1 = head
        while dummy1:
            n += 1
            dummy1 = dummy1.next
        
        # find the start point of the second half 
        m = n // 2 + 1 
        dummy2 = head
        for i in range(m-1):
            dummy2 = dummy2.next
        dummy3 = dummy2.next
        dummy2.next = None
        
        # reverse second half
        prev = None
        while dummy3:
            nxt = dummy3.next
            dummy3.next = prev
            prev = dummy3
            dummy3= nxt
        
        # merge two half
        dummy4 = head
        # print(head.next.next.val)
        for i in range(n-m):
            nxt_head = dummy4.next
            nxt_prev = prev.next
            dummy4.next = prev
            prev.next = nxt_head
            prev = nxt_prev
            dummy4 = nxt_head 

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

取巧的办法是，用快慢指针找到后半段，这样不用计算链表长度

找到中间节点，断开，把后半截linked list reverse，然后合并两段

class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        if head == None or head.next == None or head.next.next == None:
            return
        
        slow = head
        fast = head
        prev = None
        
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next       
        prev.next = None

        slow = self.reverseList(slow)
        
        cur = head
        while cur.next:
            nxt = cur.next
            cur.next = slow
            slow = slow.next
            cur.next.next = nxt
            cur = nxt
        cur.next = slow   
    
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        prev = None 
        cur = head
        while cur:
            nxt = cur.next
            cur.next = prev
            prev = cur
            cur = nxt
        return prev