题目描述：

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

题目大意：

给定一个单链表L：L0→L1→…→Ln-1→Ln
重新将其排序为： L0→Ln→L1→Ln-1→L2→Ln-2→…

必须在不改变节点值的前提下就地完成链表的顺序重排。

解题思路：

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

 

本文链接：http://bookshadow.com/weblog/2015/01/29/leetcode-reorder-list/
请尊重作者的劳动成果，转载请注明出处！书影博客保留对文章的所有权利。

如果您喜欢这篇博文，欢迎您捐赠书影博客： ，查看支付宝二维码