Reorder linked list in python-CodePudding

I tried to solve this problem. However, I have got time limit exceed. Anyone can solve this problem without time limitation exceeds? Here is the question. You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

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

You may not modify the values in the list's nodes. Only nodes themselves may be changed. Here is my implementation. However, time limit exceeds.

# 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

CodePudding user response：

There is a "Discuss" section on LeetCode, where you could find some solutions and explanations.

One possible solution from there:

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