Reorder List

 

Problem Statement: Given a singly linked list L: L0 → L1 → … → Ln-1 → Ln, reorder it to: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

1. Clarify the problem:

  • Can we assume that the input linked list is valid (non-empty)?
  • How do we handle an empty or single-node linked list as input?

2. Analyze the problem:

  • Input: Linked list
  • Output: Reordered linked list
  • Constraints:
    • The input linked list can be empty or contain a single node.
    • The length of the linked list is not specified.

3. Design an algorithm:

  • Find the middle node of the linked list using the slow and fast pointer technique.
  • Reverse the second half of the linked list.
  • Merge the first half and the reversed second half of the linked list alternatively.

4. Explain your approach:

  • We will find the middle node of the linked list using the slow and fast pointer technique.
  • Then, we will reverse the second half of the linked list.
  • Finally, we will merge the first half and the reversed second half of the linked list alternatively.

5. Write clean and readable code:

python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def reorderList(self, head):
        if not head or not head.next:
            return head

        # Find the middle node of the linked list
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # Reverse the second half of the linked list
        prev = None
        curr = slow
        while curr:
            next_node = curr.next
            curr.next = prev
            prev = curr
            curr = next_node

        # Merge the first half and the reversed second half of the linked list
        first_half = head
        second_half = prev
        while second_half.next:
            temp = first_half.next
            first_half.next = second_half
            first_half = temp

            temp = second_half.next
            second_half.next = first_half
            second_half = temp

        return head

6. Test your code: Let's test the code with some example and additional test cases:

python
# Example test case
solution = Solution()
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
solution.reorderList(head)
# Expected output: head = 1 → 4 → 2 → 3

# Additional test cases
head = None
solution.reorderList(head)
# Expected output: head = None

head = ListNode(1)
solution.reorderList(head)
# Expected output: head = 1

head = ListNode(1)
head.next = ListNode(2)
solution.reorderList(head)
# Expected output: head = 1 → 2

head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
solution.reorderList(head)
# Expected output: head = 1 → 3 → 2

7. Optimize if necessary: The provided solution has a time complexity of O(n) since we need to iterate through the entire linked list to find the middle node and reverse the second half. The space complexity is O(1) since we are not using any additional data structures.

8. Handle error cases: The code handles the case where the input linked list is empty or contains a single node. In such cases, the code returns the head of the linked list as is.

9. Discuss complexity analysis: The time complexity of the solution is O(n) since we need to traverse the entire linked list once to find the middle node and reverse the second half. The space complexity is O(1) since we are not using any additional data structures.

Next Post Previous Post