Reorder list#

Levels: level-3

Data structures: linkedlist

Practice Link#

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.

Examples#

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

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

Python Solution#

 1class ListNode(object):
 2    def __init__(self, x):
 3        self.val = x
 4        self.next = None
 5
 6
 7class Solution(object):
 8    def reorderList(self, head):
 9        """
10        :type head: ListNode
11        :rtype: None Do not return anything, modify head in-place instead.
12        """
13        if not head:
14            return
15
16        # find the mid point
17        slow = fast = head
18        while fast and fast.next:
19            slow = slow.next
20            fast = fast.next.next
21
22        # reverse the second half in-place
23        pre, node = None, slow
24        while node:
25            pre, node.next, node = node, pre, node.next
26
27        # Merge in-place; Note : the last node of "first" and "second" are the same
28        first, second = head, pre
29        while second.next:
30            first.next, first = second, first.next
31            second.next, second = first, second.next
32        return