What is the time complexity of Reorder List?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Reorder List?

This problem uses Linked List, Two Pointers, Stack, Recursion. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Reorder List?

Insight 1: The core idea is to divide the linked list into two halves, reverse the second half, and then merge (interweave) them. Insight 2: Using the fast and slow pointer technique helps in efficiently finding the middle of the linked list.

Which companies ask LeetCode 143. Reorder List in interviews?

This problem is frequently asked at Arista Networks, Goldman Sachs, LinkedIn, TikTok, Yahoo.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Reorder List - LeetCode 143 Solution

Reorder List - Complete Solution Guide

Reorder List is LeetCode problem 143, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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: 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

Detailed Explanation

The problem asks us to reorder a singly linked list from L0 -> L1 -> ... -> Ln-1 -> Ln to L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ... without modifying the values within the nodes, only rearranging the nodes themselves. Essentially, we need to interweave the first and second halves of the linked list.

Solution Approach

The provided solution uses a three-step approach: 1) Find the middle of the linked list using the fast and slow pointer technique. 2) Reverse the second half of the linked list. 3) Merge the first half and the reversed second half. Finding the middle allows us to divide the list. Reversing the second half prepares it for interweaving. The merging step then creates the final reordered list.

Step-by-Step Algorithm

Step 1: Find the middle of the linked list. Use two pointers, 'slow' and 'fast'. 'Fast' moves twice as fast as 'slow'. When 'fast' reaches the end, 'slow' will be at the middle.
Step 2: Reverse the second half of the linked list starting from 'slow.next'. Set 'slow.next' to null to separate the first and second halves. Iteratively reverse the second half by changing the 'next' pointers.
Step 3: Merge the first half and the reversed second half. Iterate through both halves, interweaving the nodes by updating the 'next' pointers accordingly. Take nodes alternately from each list until one of the lists is exhausted.

Key Insights

Insight 1: The core idea is to divide the linked list into two halves, reverse the second half, and then merge (interweave) them.
Insight 2: Using the fast and slow pointer technique helps in efficiently finding the middle of the linked list.
Insight 3: In-place manipulation is crucial for achieving O(1) space complexity, which requires careful management of pointers during reversal and merging.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Two Pointers, Stack, Recursion.

Companies

Asked at: Arista Networks, Goldman Sachs, LinkedIn, TikTok, Yahoo.

Reorder List | LeetCode 143

Medium

Linked List Two Pointers Stack Recursion

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

Solution Code

Available in:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null) {
            return;
        }

        // Step 1: Find the middle of the list
        ListNode slow = head, fast = head;
        while (fast.next != null && fast.next.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // Step 2: Reverse the second half of the list
        ListNode second_half = slow.next;
        ListNode prev = null;
        slow.next = null;

        while (second_half != null) {
            ListNode temp = second_half.next;
            second_half.next = prev;
            prev = second_half;
            second_half = temp;
        }

        // Step 3: Merge the two halves
        ListNode first_half = head;
        ListNode second_half_rev = prev;

        while (second_half_rev != null) {
            ListNode temp1 = first_half.next;
            ListNode temp2 = second_half_rev.next;

            first_half.next = second_half_rev;
            second_half_rev.next = temp1;

            first_half = temp1;
            second_half_rev = temp2;
        }
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 143: Reorder List - Detailed explanation and solution approaches.

Topics

Linked List Two Pointers Stack Recursion

Companies

Arista NetworksGoldman SachsLinkedInTikTokYahoo

Stats

Difficulty:Medium

Languages:4

Companies:5

Problem #:143

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

3 steps

1
Step 1: Find the middle of the linked list. Use two pointers, 'slow' and 'fast'. 'Fast' moves twice as fast as 'slow'. When 'fast' reaches the end, 'slow' will be at the middle.
2
Step 2: Reverse the second half of the linked list starting from 'slow.next'. Set 'slow.next' to null to separate the first and second halves. Iteratively reverse the second half by changing the 'next' pointers.
3
Step 3: Merge the first half and the reversed second half. Iterate through both halves, interweaving the nodes by updating the 'next' pointers accordingly. Take nodes alternately from each list until one of the lists is exhausted.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(1)

💪 Constant space - Uses same memory regardless of input!

📝

Why?

Time Complexity: Finding the middle takes O(n/2) time. Reversing the second half takes O(n/2) time. Merging takes O(n/2) time. Therefore, the total time complexity is O(n). Space Complexity: The solution uses a constant amount of extra space for pointers, regardless of the input size, achieving O(1) space complexity.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Using a Stack

Iterate through the linked list and push each node onto a stack. Then, iterate through the original list again, but this time, pop a node from the stack and insert it between the current node and the next node. This achieves the same reordering.

Time: O(n)Space: O(n)

Trade-offs: The stack approach is simpler to understand but requires O(n) extra space, making the in-place solution more efficient in terms of space.

✨

Key Insights

1Insight 1: The core idea is to divide the linked list into two halves, reverse the second half, and then merge (interweave) them.
2Insight 2: Using the fast and slow pointer technique helps in efficiently finding the middle of the linked list.
3Insight 3: In-place manipulation is crucial for achieving O(1) space complexity, which requires careful management of pointers during reversal and merging.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Recursion

A function that calls itself to solve smaller versions of the same problem.

Stack

LIFO structure - Last In, First Out. Like a stack of plates!

Linked List

Elements connected via pointers. Like a chain where each link knows the next.

Edge Cases

Edge case 1: Empty list (head is null) or a list with only one node (head.next is null). The code handles this by returning immediately, as there's nothing to reorder.
Edge case 2: List with two nodes. The algorithm will correctly separate the list, reverse the (single) node in the second half, and then merge them, resulting in the correct reordering.
Edge case 3: List with even number of nodes and odd number of nodes. The code correctly finds the middle and splits the list appropriately. The merging handles the potentially different lengths of the two lists gracefully.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to set slow.next = null after finding the middle. This is essential to properly separate the two halves before reversing and merging; otherwise, you might have cycles in the list.

✗Common mistake 2: Incorrectly reversing the second half, leading to a broken list or infinite loop.

✗Common mistake 3: Not handling the cases where the two halves have different lengths during the merge step, resulting in a partially reordered list or an exception.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Playlist reordering - Imagine a music playlist where you want to alternate between old and new songs. This algorithm can be used to reorder the playlist based on some criteria like date added.

🏦Real-world scenario 2: Message queue processing - In a messaging system, you might want to process messages in a specific order, alternating between high-priority and low-priority messages. This algorithm can be adapted to reorder the message queue.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

The dummy node technique prevents edge cases. For cycle detection, Floyd's algorithm is the standard. Always handle empty list and single node cases.

🎯 Interview Tip

Consider multiple approaches before coding. Mentioning alternatives shows breadth of knowledge.

⚠️ Watch Out

Losing reference to nodes when modifying pointers. Use temporary variables to save references.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 22, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

How does the fast/slow pointer technique work?

Fast pointer moves 2 steps while slow moves 1 step. When fast reaches the end, slow is at middle. If there's a cycle, they will meet. This technique is used for: finding middle node, detecting cycles, finding cycle start point, and checking palindromes.

How do I avoid infinite loops with two pointers?

Always ensure your loop condition guarantees termination (typically left < right or slow != fast). Move at least one pointer in each iteration, and handle edge cases where pointers might not move (like skipping duplicates). Draw out pointer movement on paper first.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Reorder List"?

For this medium-level Linked List problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether two pointers techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?