Reorder List

Problem: Reorder List

The general idea to solve this problem is to prepare two lists, one ordinary and one reversed. Then we merged them together to get the result.

However, if we copy one list and reverse it to maintain the original one, it will cost a lot of space and time, so we can simply find the median and cut the second half of list down and reverse it. Thus we can get two list of half length with right order and reversed order. Note, always pass position or pointer if you can.

Code in Python

# Definition for singly-linked list.
# class ListNode(object)
#     def __init__(self, x):
#         self.val = x
#         self.next = None

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:
            return
        med = self.findMedian(head)
        tail = self.reverseList(med)
        self.merge(head, tail)

    def findMedian(self, head):
        slow, fast = head, head.next
        while fast:
            if fast.next:
                slow = slow.next
                fast = fast.next.next
            else:
                break
        return slow.next

    def reverseList(self, tail):
        next = tail.next
        tail.next = None
        while next:
            temp = next.next
            next.next = tail
            tail = next
            next = temp
        return tail

    def merge(self, head, tail):
        iter1, iter2 = head, tail
        while iter2:
            temp1, temp2 = iter1.next, iter2.next
            iter1.next, iter2.next = iter2, temp1
            iter1, iter2 = temp1, temp2
        if iter1:
            iter1.next = iter2