## 题目描述：

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

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}.

## 解题思路：

1. 利用快慢指针找到链表中点mid，将链表分为左右两半
2. 将链表的右半部分就地逆置
3. 合并链表的左右两部分

## Python代码：

``````# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
# @param head, a ListNode
# @return nothing
def reorderList(self, head):
if head is None:
return head

#find mid
slow = head
fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow

#cut in the mid
left = head
right = mid.next
if right is None:
return head
mid.next = None

#reverse right half
cursor = right.next
right.next = None
while cursor:
next = cursor.next
cursor.next = right
right = cursor
cursor = next

#merge left and right
dummy = ListNode(0)
while left or right:
if left is not None:
dummy.next = left
left = left.next
dummy = dummy.next
if right is not None:
dummy.next = right
right = right.next
dummy = dummy.next
return head
``````

Pingbacks已关闭。