Partitioning a linked list around a given value and If we don’t care about making the elements of the list “stable”
Last Updated :
12 Jul, 2022
Given a linked list and a value x, partition a linked list around a value x, such that all nodes less than x come before all nodes greater than or equal to x. If x is contained within the list the values of x only need to be after the elements less than x (see below). The partition element x can appear anywhere in the “right partition”; it does not need to appear between the left and right partitions.
Similar problem: Partitioning a linked list around a given value and keeping the original order
Examples:
Input : 3 -> 5 -> 10 -> 2 -> 8 -> 2 -> 1
x = 5
Output : 1-> 2-> 2-> 3-> 5-> 10-> 8
If we don’t care about making the elements of the list “stable” then we can instead rearrange the elements by growing the list at the head and tail.
In this approach, we start a “new” list (using the existing nodes). Elements bigger than the pivot element are put at the tail and elements smaller are put at the head. Each time we insert an element, we update either the head or tail.
Below is the implementation of above idea.
C++
#include<bits/stdc++.h>
using namespace std;
struct Node
{
int data;
struct Node* next;
};
Node *newNode(int data)
{
struct Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
return new_node;
}
struct Node *partition(struct Node *head, int x)
{
struct Node *tail = head;
Node *curr = head;
while (curr != NULL)
{
struct Node *next = curr->next;
if (curr->data < x)
{
curr->next = head;
head = curr;
}
else
{
tail->next = curr;
tail = curr;
}
curr = next;
}
tail->next = NULL;
return head;
}
void printList(struct Node *head)
{
struct Node *temp = head;
while (temp != NULL)
{
printf("%d ", temp->data);
temp = temp->next;
}
}
int main()
{
struct Node* head = newNode(3);
head->next = newNode(5);
head->next->next = newNode(8);
head->next->next->next = newNode(2);
head->next->next->next->next = newNode(10);
head->next->next->next->next->next = newNode(2);
head->next->next->next->next->next->next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
return 0;
}
|
Java
class GfG {
static class Node
{
int data;
Node next;
}
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
static Node partition(Node head, int x)
{
Node tail = head;
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
curr.next = head;
head = curr;
}
else
{
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
return head;
}
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
public static void main(String[] args)
{
Node head = newNode(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
}
}
|
Python3
import math
class Node:
def __init__(self, data):
self.data = data
self.next = None
def newNode(data):
new_node = Node(data)
new_node.data = data
new_node.next = None
return new_node
def partition(head, x):
tail = head
curr = head
while (curr != None):
next = curr.next
if (curr.data < x):
curr.next = head
head = curr
else:
tail.next = curr
tail = curr
curr = next
tail.next = None
return head
def printList(head):
temp = head
while (temp != None):
print(temp.data, end = " ")
temp = temp.next
if __name__=='__main__':
head = newNode(3)
head.next = newNode(5)
head.next.next = newNode(8)
head.next.next.next = newNode(2)
head.next.next.next.next = newNode(10)
head.next.next.next.next.next = newNode(2)
head.next.next.next.next.next.next = newNode(1)
x = 5
head = partition(head, x)
printList(head)
|
C#
using System;
class GfG
{
class Node
{
public int data;
public Node next;
}
static Node newNode(int data)
{
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
static Node partition(Node head, int x)
{
Node tail = head;
Node curr = head;
while (curr != null)
{
Node next = curr.next;
if (curr.data < x)
{
curr.next = head;
head = curr;
}
else
{
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
return head;
}
static void printList(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
}
public static void Main(String[] args)
{
Node head = newNode(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
int x = 5;
head = partition(head, x);
printList(head);
}
}
|
Javascript
<script>
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function newNode(data) {
var new_node = new Node();
new_node.data = data;
new_node.next = null;
return new_node;
}
function partition(head , x) {
var tail = head;
var curr = head;
while (curr != null) {
var next = curr.next;
if (curr.data < x) {
curr.next = head;
head = curr;
}
else
{
tail.next = curr;
tail = curr;
}
curr = next;
}
tail.next = null;
return head;
}
function printList(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
var head = newNode(3);
head.next = newNode(5);
head.next.next = newNode(8);
head.next.next.next = newNode(2);
head.next.next.next.next = newNode(10);
head.next.next.next.next.next = newNode(2);
head.next.next.next.next.next.next = newNode(1);
var x = 5;
head = partition(head, x);
printList(head);
</script>
|
Complexity Analysis:
- Time Complexity: O(n).
- Space Complexity: O(1), as we are not using more than 4 pointers.
Like Article
Suggest improvement
Share your thoughts in the comments
Please Login to comment...