143. Reorder List
Given a singly linked list , reorder it to:
You must do this in-place without altering the nodes' values.
For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.
Solution:
class Solution(object):
def reorderList(self, head):
"""
:type head: ListNode
:rtype: void Do not return anything, modify head in-place instead.
"""
if not head or not head.next:
return
middle = self.get_middle(head)
right = self.reverse(middle.next)
middle.next = None
self.merge(head, right)
def get_middle(self, head):
if not head or not head.next:
return head
slow = head
fast = head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverse(self, head):
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre
pre, cur = cur, nxt
return pre
def merge(self, left, right):
while left and right:
left_next = left.next
right_next = right.next
left.next = right
right.next = left_next
left = left_next
right = right_next