Reorder List

Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln

reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

Example

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

Solution

"""
Definition of ListNode
class ListNode(object):

    def __init__(self, val, next=None):
        self.val = val
        self.next = next
"""
class Solution:
    """
    @param head: The first node of the linked list.
    @return: nothing
    """
    def reorderList(self, head):

        if head == None or head.next == None:
            return None
        # write your code here
        dummy = ListNode(0)

        slow, fast = head, head.next

        while fast and fast.next:
            slow = slow.next
            fast = fast.next
        right = self.reverse(slow.next)

        slow.next = None

        return self.merge(head, right)

    def merge(self, left, right):
        dummy = ListNode(0)
        tail = dummy
        index = 0
        while left and right:
            if index % 2 == 0:
                tail.next = left
                tail = tail.next
                left = left.next
            else:
                tail.next = right
                tail = tail.next
                right = right.next
            index += 1
        if left:
            tail.next = left
        else:
            tail.next = right
        return dummy.next    

    def reverse(self, head):
        prev = None
        while head:
            temp = head.next
            head.next = prev
            prev = head
            head = temp
        return prev