Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln
reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …
Example
Given 1->2->3->4->null, reorder it to 1->4->2->3->null.
Solution
"""
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):
if head == None or head.next == None:
return None
# write your code here
dummy = ListNode(0)
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next
right = self.reverse(slow.next)
slow.next = None
return self.merge(head, right)
def merge(self, left, right):
dummy = ListNode(0)
tail = dummy
index = 0
while left and right:
if index % 2 == 0:
tail.next = left
tail = tail.next
left = left.next
else:
tail.next = right
tail = tail.next
right = right.next
index += 1
if left:
tail.next = left
else:
tail.next = right
return dummy.next
def reverse(self, head):
prev = None
while head:
temp = head.next
head.next = prev
prev = head
head = temp
return prev