What is the time complexity of Partition List?

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

What data structures are used to solve Partition List?

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

What are the key insights for solving Partition List?

Insight 1: Using two separate linked lists (or pointers acting as heads/tails) allows efficient partitioning without needing to swap elements in place, which would be cumbersome for linked lists. Insight 2: Creating dummy nodes for the 'less than' and 'greater than or equal to' lists simplifies the logic, especially when handling the initial empty state of these lists.

Which companies ask LeetCode 86. Partition List in interviews?

This problem is frequently asked at Adobe, Amazon, Apple, Bloomberg, Microsoft and 1 more companies.

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

Partition List - LeetCode 86 Solution

Q: How to solve Partition List?

The solution utilizes two separate linked lists to store nodes less than 'x' and nodes greater than or equal to 'x', respectively. We iterate through the original linked list and append each node to the appropriate list. Dummy head nodes are used to simplify the process of creating the two new lists. After the partitioning is complete, the 'greater than or equal to' list is terminated by setting its tail's next pointer to NULL. Finally, the 'less than' list is connected to the 'greater than or equal to' list, forming the partitioned linked list. The dummy head nodes are then discarded by returning the next node of the less_head.

Partition List - Complete Solution Guide

Partition List is LeetCode problem 86, 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

Given the head of a linked list and a value x , partition it such that all nodes less than x come before nodes greater than or equal to x . You should preserve the original relative order of the nodes in each of the two partitions. Example 1: Input: head = [1,4,3,2,5,2], x = 3 Output: [1,2,2,4,3,5] Example 2: Input: head = [2,1], x = 2 Output: [1,2] Constraints: The number of nodes in the list is in the range [0, 200] . -100 <= Node.val <= 100 -200 <= x <= 200

Detailed Explanation

The problem asks us to rearrange a given linked list such that all nodes with values less than a given value 'x' appear before nodes with values greater than or equal to 'x'. The original relative order of nodes within each partition (less than x and greater than or equal to x) must be preserved. The input is the head of the linked list and the value 'x'. The output is the head of the modified linked list.

Solution Approach

The solution utilizes two separate linked lists to store nodes less than 'x' and nodes greater than or equal to 'x', respectively. We iterate through the original linked list and append each node to the appropriate list. Dummy head nodes are used to simplify the process of creating the two new lists. After the partitioning is complete, the 'greater than or equal to' list is terminated by setting its tail's next pointer to NULL. Finally, the 'less than' list is connected to the 'greater than or equal to' list, forming the partitioned linked list. The dummy head nodes are then discarded by returning the next node of the less_head.

Step-by-Step Algorithm

Step 1: Initialize two dummy nodes, `less_head` and `greater_head`, and corresponding tail pointers, `less_tail` and `greater_tail`, pointing to these dummy nodes. These will serve as the heads and tails of the 'less than x' and 'greater than or equal to x' partitions.
Step 2: Iterate through the original linked list using a `current` pointer.
Step 3: For each node `current`, check if its value is less than `x`. If it is, append it to the 'less than x' list by setting `less_tail.next = current` and moving `less_tail` to `current`.
Step 4: If the node `current`'s value is greater than or equal to `x`, append it to the 'greater than or equal to x' list by setting `greater_tail.next = current` and moving `greater_tail` to `current`.
Step 5: After processing the entire original list, terminate the 'greater than or equal to x' list by setting `greater_tail.next = None`. This is crucial to prevent a cycle or incorrect linkage.
Step 6: Connect the 'less than x' list to the 'greater than or equal to x' list by setting `less_tail.next = greater_head.next`. This joins the two partitions together.
Step 7: Return the head of the partitioned list, which is `less_head.next`. This skips the dummy `less_head` node.

Key Insights

Insight 1: Using two separate linked lists (or pointers acting as heads/tails) allows efficient partitioning without needing to swap elements in place, which would be cumbersome for linked lists.
Insight 2: Creating dummy nodes for the 'less than' and 'greater than or equal to' lists simplifies the logic, especially when handling the initial empty state of these lists.
Insight 3: Crucially, after partitioning, the 'next' pointer of the last node in the 'greater than or equal to' list must be set to NULL to avoid forming a cycle or including nodes from the original list that shouldn't be there.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(1)

Topics

This problem involves: Linked List, Two Pointers.

Companies

Asked at: Adobe, Amazon, Apple, Bloomberg, Microsoft, tcs.

Partition List | LeetCode 86

Medium

Linked List Two Pointers

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 ListNode partition(ListNode head, int x) {
        ListNode less_head = new ListNode(0);
        ListNode less_tail = less_head;
        ListNode greater_head = new ListNode(0);
        ListNode greater_tail = greater_head;

        ListNode current = head;
        while (current != null) {
            if (current.val < x) {
                less_tail.next = current;
                less_tail = less_tail.next;
            } else {
                greater_tail.next = current;
                greater_tail = greater_tail.next;
            }
            current = current.next;
        }

        greater_tail.next = null;
        less_tail.next = greater_head.next;

        return less_head.next;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 86: Partition List - Detailed explanation and solution approaches.

Topics

Linked List Two Pointers

Companies

AdobeAmazonAppleBloombergMicrosofttcs

Stats

Difficulty:Medium

Languages:4

Companies:6

Problem #:86

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

7 steps

1
Step 1: Initialize two dummy nodes, `less_head` and `greater_head`, and corresponding tail pointers, `less_tail` and `greater_tail`, pointing to these dummy nodes. These will serve as the heads and tails of the 'less than x' and 'greater than or equal to x' partitions.
2
Step 2: Iterate through the original linked list using a `current` pointer.
3
Step 3: For each node `current`, check if its value is less than `x`. If it is, append it to the 'less than x' list by setting `less_tail.next = current` and moving `less_tail` to `current`.
4
Step 4: If the node `current`'s value is greater than or equal to `x`, append it to the 'greater than or equal to x' list by setting `greater_tail.next = current` and moving `greater_tail` to `current`.
5
Step 5: After processing the entire original list, terminate the 'greater than or equal to x' list by setting `greater_tail.next = None`. This is crucial to prevent a cycle or incorrect linkage.
6
Step 6: Connect the 'less than x' list to the 'greater than or equal to x' list by setting `less_tail.next = greater_head.next`. This joins the two partitions together.
7
Step 7: Return the head of the partitioned list, which is `less_head.next`. This skips the dummy `less_head` node.

💡

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?

The time complexity is linear because each node is visited and processed exactly once. The space complexity is constant because the additional space used is independent of the input size; only a few pointer variables are used.

📖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

In-place Partitioning (more complex)

Attempting to perform the partition directly within the original linked list without using extra lists. This involves more complex pointer manipulation to swap nodes in place.

Time: O(n) on average but can degrade to O(n^2) if elements near the beginning require many swaps.Space: O(1)

Trade-offs: This approach avoids extra space, but the implementation is significantly more complex and error-prone. It also might not be as efficient because swapping elements in a linked list is not constant time.

✨

Key Insights

1Insight 1: Using two separate linked lists (or pointers acting as heads/tails) allows efficient partitioning without needing to swap elements in place, which would be cumbersome for linked lists.
2Insight 2: Creating dummy nodes for the 'less than' and 'greater than or equal to' lists simplifies the logic, especially when handling the initial empty state of these lists.
3Insight 3: Crucially, after partitioning, the 'next' pointer of the last node in the 'greater than or equal to' list must be set to NULL to avoid forming a cycle or including nodes from the original list that shouldn't be there.

📚

Key Terms Explained

For Students

Two Pointers

Using two indices to traverse data from different positions simultaneously.

Linked List

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

Edge Cases

Edge case 1: Empty linked list (head is None). The algorithm correctly handles this case because the while loop will not execute, and the initialized dummy nodes will handle returning an empty list.
Edge case 2: All nodes are less than x. The algorithm will correctly append all nodes to the 'less than' list, and the 'greater than' list will remain empty (excluding the dummy node). Connecting the 'less than' list to the empty 'greater than' list will result in the original list (in the correct order) being returned.
Edge case 3: All nodes are greater than or equal to x. The algorithm will correctly append all nodes to the 'greater than or equal to' list, and the 'less than' list will remain empty. Since less_tail.next is set to greater_head.next, the result is a list of all nodes >= x
Edge case 4: x is the smallest or largest value. This is handled naturally by the comparisons in the while loop.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Forgetting to set `greater_tail.next = None`. This can lead to a cycle in the list or including nodes from the original list that shouldn't be part of the partitioned list.

✗Common mistake 2: Not handling the edge case of an empty input list (head is None) correctly, which could result in errors when trying to access node values.

✗Common mistake 3: Not using dummy nodes, which makes the code more complex and harder to read due to the need to handle special cases for the first element in each partition.

✗Common mistake 4: Modifying the original list incorrectly during the partitioning process, leading to lost nodes or incorrect ordering. Using two separate lists prevents accidental modifications.

✅

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: Data stream processing: Imagine a stream of data where you want to separate data based on a certain threshold. This algorithm can be used to quickly categorize and process data points into different queues or pipelines based on their values.

🏦Real-world scenario 2: Sorting algorithms: While not a sorting algorithm itself, the partitioning step in QuickSort uses a similar principle to divide a dataset based on a pivot. This problem demonstrates the core idea of partitioning, which is a fundamental concept in sorting and data management.

💡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: August 26, 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

The key insight here is recognizing the pattern. Once you see it, the solution becomes straightforward.

@AlgoMasterJul 13

I was asked this exact problem at my Google interview. The interviewer wanted me to optimize space complexity.

@InterviewProJul 6

❓

Frequently Asked Questions

Why use a dummy node in linked list problems?

A dummy node simplifies edge cases where the head might change (insertion/deletion at head) or when building a new list. Initialize dummy.next = head, work with dummy.next throughout, and return dummy.next at the end to handle all cases uniformly.

When is the two-pointer technique most effective?

Two pointers work best on sorted arrays or when searching for pairs/triplets that satisfy a condition. Common patterns include: moving pointers inward from both ends (like in two-sum variants), fast/slow pointers for cycle detection, or left/right pointers for partitioning.

What techniques are commonly tested in medium-difficulty problems?

Medium problems often require combining multiple techniques: two-pointer with hash maps, BFS/DFS with state tracking, dynamic programming with optimization, or divide-and-conquer approaches. They test your ability to recognize patterns and choose the right combination of techniques.

How should I practice algorithm problems effectively?

Focus on understanding patterns rather than memorizing solutions. After solving a problem, review optimal solutions and understand the intuition. Group similar problems to recognize patterns. Practice explaining your approach out loud. Review problems after a few days to test retention.

What is the optimal approach for "Partition 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?