Linked List Partitioning | Data Structures and Algorithms

Introduction

In computer science, partitioning is the act of dividing a data set into multiple parts. In this challenge, we will partition a linked list around a given value x.

Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL python(("`Python`")) -.-> python/BasicConceptsGroup(["`Basic Concepts`"]) algorithm(("`Algorithm`")) -.-> algorithm/BasicAlgorithmsGroup(["`Basic Algorithms`"]) python(("`Python`")) -.-> python/ControlFlowGroup(["`Control Flow`"]) python(("`Python`")) -.-> python/DataStructuresGroup(["`Data Structures`"]) python(("`Python`")) -.-> python/FunctionsGroup(["`Functions`"]) python(("`Python`")) -.-> python/ObjectOrientedProgrammingGroup(["`Object-Oriented Programming`"]) python(("`Python`")) -.-> python/AdvancedTopicsGroup(["`Advanced Topics`"]) python/BasicConceptsGroup -.-> python/comments("`Comments`") algorithm/BasicAlgorithmsGroup -.-> algorithm/linked_lists("`Linked Lists`") python/ControlFlowGroup -.-> python/conditional_statements("`Conditional Statements`") python/ControlFlowGroup -.-> python/while_loops("`While Loops`") python/DataStructuresGroup -.-> python/lists("`Lists`") python/DataStructuresGroup -.-> python/tuples("`Tuples`") python/FunctionsGroup -.-> python/function_definition("`Function Definition`") python/FunctionsGroup -.-> python/default_arguments("`Default Arguments`") python/ObjectOrientedProgrammingGroup -.-> python/classes_objects("`Classes and Objects`") python/ObjectOrientedProgrammingGroup -.-> python/constructor("`Constructor`") python/ObjectOrientedProgrammingGroup -.-> python/polymorphism("`Polymorphism`") python/ObjectOrientedProgrammingGroup -.-> python/encapsulation("`Encapsulation`") python/AdvancedTopicsGroup -.-> python/iterators("`Iterators`") python/FunctionsGroup -.-> python/build_in_functions("`Build-in Functions`") subgraph Lab Skills python/comments -.-> lab-268846{{"`Partition Linked List Around Value`"}} algorithm/linked_lists -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/conditional_statements -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/while_loops -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/lists -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/tuples -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/function_definition -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/default_arguments -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/classes_objects -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/constructor -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/polymorphism -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/encapsulation -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/iterators -.-> lab-268846{{"`Partition Linked List Around Value`"}} python/build_in_functions -.-> lab-268846{{"`Partition Linked List Around Value`"}} end

Partition

Problem

Given a singly linked list, partition it around a value x, such that all nodes less than x come before all nodes greater than or equal to x. The function should return a new linked list.

Requirements

To solve this problem, we need to consider the following requirements:

The linked list is non-circular and singly linked.

The function should return a new linked list.

The input value x is valid.

We already have a linked list class that can be used for this problem.

We can create additional data structures.

The problem fits in memory.

Example Usage

Here are some examples of how the function should work:

Empty list -> []

One element list -> [element]

Left linked list is empty -> [10, 11, 12]

Right linked list is empty -> [1, 2, 3]

General case

Partition = 10
Input: 4, 3, 7, 8, 10, 1, 10, 12
Output: 4, 3, 7, 8, 1, 10, 10, 12

Partition Linked List Around Value