重新排序 python 中的链表

Question

我试图解决这个问题。但是，我有超过时间限制。任何人都可以在没有时间限制的情况下解决这个问题吗？这是问题。给你一个单向链表的头部。该列表可以表示为：

L0 → L1 → … → Ln - 1 → Ln

将列表重新排序为以下形式：

L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …

您不能修改列表节点中的值。只有节点本身可以更改。这是我的实现。但是，超过了时间限制。

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        """
        temp=head
        temp2=None
        if temp.next is None:
            pass
        elif temp.next.next is None:
            pass
        else:
            while temp.next:
                temp2=temp
                while temp2.next:
                    prev=temp2
                    temp2=temp2.next
                temp2.next=temp.next
                temp.next=temp2
                prev.next=None
                if temp2.next.next is None:
                    break
                if temp2.next.next.next is None:
                    break
                temp=temp.next.next

Answer 1

LeetCode 上有一个 "Discuss" 部分，您可以在其中找到一些解决方案和解释。

一个可能的解决方案：

class Solution:
    def reorderList(self, head: ListNode) -> None:
        if not head:
            return head

        # find mid point
        slow = fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse the second half in-place
        # slow.next: the start point of reverse

        head2 = None
        curr = slow.next
        slow.next = None
        while curr:
            next = curr.next
            curr.next = head2
            head2 = curr
            curr = next

        # merge in-place
        first, second = head, head2

        while second:
            first.next, first = second, first.next
            second.next, second = first, second.next
        return

重新排序 python 中的链表

Reorder linked list in python

python

sorting

linked-list