Reorder List

Question

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

You must do this in-place without altering the nodes' values.

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

Thoughts

和sort list类似，也可以用mergesort的方法来解决 1 找到中点，split list 2 将rightlist reverse 3 merge 2 list

Solution

class Solution:
    """
    @param head: The first node of the linked list.
    @return: nothing
    """
    def reorderList(self, head):
        # write your code here
        if not head:
            return None
        length = self.length(head)
        if length > 1:
            mid = length / 2
            leftList, rightList = self.splitList(head, mid)
            reversedRightList = self.reverseList(rightList)
            self.printList(reversedRightList)
            head = self.mergeList(leftList, reversedRightList)
        return head

    def splitList(self, head, number):
        node = head
        i = 1
        while i < number:
            i += 1
            node = node.next
        rightHead = node.next
        node.next = None
        return head, rightHead

    def length(self, head):
        length = 0
        while head:
            length += 1
            head = head.next
        return length

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

    def mergeList(self, l1, l2):
        dummy = ListNode(0)
        lastNode = dummy
        while l1 and l2:
            lastNode.next = l1
            l1 = l1.next
            lastNode = lastNode.next
            lastNode.next = l2
            l2 = l2.next
            lastNode = lastNode.next
        if l1:
            lastNode.next = l1
        if l2:
            lastNode.next = l2
        return dummy.next