LC 143 - Reorder List

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.

Example 1:

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

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 * 104].
• 1 <= Node.val <= 1000

Links

Question here and solution here

Solution

concept

The most straight forward way to do is first store them in a list, and then use two-pointers to reconnect the linked list.

Alternative we can first find out the segments of the linked list such that they are more or less equal. We can do this by having a fast and slow pointer (Note that the fast pointer starts at head.next while slow pointer start at head.)

For both the case of even or odd number of nodes, the 2nd segment starts at slow.next We then reverse the second segment of the linked list, this allow us to traverse the 2nd part of the linked list in reverse. Finally we will use a two pointers to traverse from the two ends.

code

# 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.
        
        two-pointer with list to store the node first
        """
        nodes = []
        cur = head

        while cur:
            nodes.append(cur)
            cur = cur.next

        l, r = 0, len(nodes) - 1
        while l < r:
            nodes[l].next = nodes[r]
            l += 1
            if l >= r:
                break
            nodes[r].next = nodes[l]
            r -= 1

        nodes[l].next = None
        
class NeetSolution:
    def reorderList(self, head: Optional[ListNode]) -> None:
        """
        Do not return anything, modify head in-place instead.
        time complexity: O(n)
        space complexity: O(1)
        """
        # determine first and second segment of linked list
        # slow.next will be the beginning of 2nd segment
        slow, fast = head, head.next
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # reverse 2nd segment
        second = slow.next
        # split the linked list to 2 segment
        slow.next = None
        # previous nodes default
        prev = None
        # iterate the (potential) shorter segment
        while second:
            # before break the link, cache first
            tmp = second.next
            # now point to prev
            second.next = prev
            # move prev to curr (i.e. second)
            prev = second
            # move curr (i.e. second) to (original) next
            second = tmp

        # merge
        # original second will be None
        # but prev will be the last node of the original 2nd seg, now becomes the new head of the reversed linked list
        first, second = head, prev
        while second:
            # cache before breaking the next to point to new nodes
            tmp1, tmp2 = first.next, second.next
            first.next = second
            second.next = tmp1
            first = tmp1
            second = tmp2

Complexity

time: $O(n)$
space: $O(n)$ if use two pointer and list, $O(1)$ if use the reverse and merge method