Skip to content

143 reorder list

143. Reorder List

题目:

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

难度:

Medium

超时


class Solution(object):
    def reorderList(self, head):
        """
        :type head: ListNode
        :rtype: void Do not return anything, modify head in-place instead.
        """
        head = self.reorder(head)


    def reorder(self, head):
        if head == None or head.next == None or head.next.next == None:
            return head

        l0 = head
        l1 = head.next
        ln_1 = self.oneNodeTail(head)
        ln =ln_1.next

        l0.next = ln
        ln_1.next = None
        ln.next = self.reorder(l1)
        return l0


    def oneNodeTail(self, head):
        if head == None or head.next == None or head.next.next == None:
            return head
        cur = head 
        while cur.next:
            if cur.next.next:
                cur = cur.next
            else:
                break
        return cur

取巧的办法是:

找到中间节点,断开,把后半截linked list reverse,然后合并 √

看了AC指南

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:
            tmp = cur.next
            cur.next = slow
            slow = slow.next
            cur.next.next = tmp
            cur = tmp
        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




回到顶部