卖萌的弱渣

I am stupid, I am hungry.

Reorder List

Reorder List

Given a singly linked list L: L0→L1→…→L(n-1)→Ln,

reorder it to: L0→Ln→L1→Ln-1→L2→L(n-2)→…

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

Example

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

Solution

  • Time O(n)
  • Split the list from the middle
  • reverse the right list
  • merge two lists and get the result
(Reorder-List.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62

"""
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):
        # write your code here
        # split the list from the middle
        # reverse the right sublist
        # merge the two lists

        if head==None or head.next==None:
            return head

        # find the pivot
        dummy = ListNode(0,None)
        fast_node = dummy
        pivot = dummy
        dummy.next = head

        while fast_node != None and fast_node.next != None:
            fast_node = fast_node.next.next
            pivot = pivot.next

        right_list = pivot.next
        # terminate the left list
        pivot.next = None
        left_list = head

        # reverse the right list
        prev_node = right_list
        next_node = right_list.next
        # terminate the right list
        prev_node.next = None

        while next_node != None:
            tmp_point = next_node.next
            next_node.next = prev_node
            prev_node = next_node
            next_node = tmp_point

        right_list = prev_node

        # merge right_list and left_list
        dummy.next = left_list
        while left_list != None and right_list != None:
            next_left = left_list.next
            left_list.next = right_list
            next_right = right_list.next
            right_list.next = next_left
            left_list = next_left
            right_list = next_right

        return dummy.next