143.Reorder_List(Medium).md

143. Reorder List (Medium)

Date and Time: Jul 31, 2024, 22:40 (EST)

Link: https://leetcode.com/problems/reorder-list/

Question:

You are given the head of a singly linked-list. The list can be represented as:

$L_0 → L_1 → … → L_{n - 1} → L_n$

Reorder the list to be on the following form:

$L_0 → L_n → L_1 → L_{n - 1} → L_2 → L_{n - 2} → …$

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example 1:

Input:

Output:

Explanation:

Example 2:

Input: head = [1,2,3,4,5]

Output: [1,5,2,4,3]

Constraints:

• The number of nodes in the list is in the range [1, 5 * 10^4].

• 1 <= Node.val <= 1000

Walk-through:

1. Use fast-slow pointers method to find the middle node to split the linked-list into two lists.

2. Now we split the linked-list and reverse the right list. Remeber to set the middle node's next to None. (This is the way how we split).

3. Start changing linked-list from left and right, until right is Null.

4. We check while prev.next instead of while prev, because we prev will be None in the end, and it will return an error that Cycle in the list.

Python Solution:

# 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.
        """
        fast, slow = head, head
        while fast and fast.next:
            fast, slow = fast.next.next, slow.next
        prev = None
        while slow:
            tmp = slow.next
            slow.next = prev
            prev = slow
            slow = tmp
        while prev.next:
            tmp1, tmp2 = head.next, prev.next
            head.next = prev
            prev.next = tmp1
            head, prev = tmp1, tmp2

Time Complexity: $O(n)$
Space Complexity: $O(1)$

Java Solution:

C++ Solution:

Runtime and Memory comparison

Language	Runtime	Memory
Python3	ms	MB
Java	ms	MB
C++	ms	MB