diff options
Diffstat (limited to 'reorder_list.py')
-rw-r--r-- | reorder_list.py | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/reorder_list.py b/reorder_list.py new file mode 100644 index 0000000..c25a277 --- /dev/null +++ b/reorder_list.py @@ -0,0 +1,42 @@ +# 143. Reorder List + +""" +given the head of a singly linked list. the list can be represented as 'l0 -> +l1 -> ... -> Ln'. reorder the list to be of the following form: 'l0 -> ln -> +ln-1 -> ln-2'. you may not modify the values in the list's nodes. only nodes +themselves may be changed. +""" + + +# Definition for singly-linked list. +class ListNode(object): + def __init__(self, val=0, next=None): + self.val = val + self.next = next + + +class Solution(object): + def reorderList(self, head): + """ + :type head: ListNode + :rtype: None Do not return anything, modify head in-place instead. + """ + if not head: + return [] + slow, fast = head, head + while fast.next and fast.next.next: + slow = slow.next + fast = fast.next.next + prev, curr = None, slow.next + while curr: + tmp = curr.next + curr.next = prev + prev = curr + curr = tmp + slow.next = None + head1, head2 = head, prev + while head2: + tmp = head1.next + head1.next = head2 + head1 = head2 + head2 = tmp |