In the Leetcode Partition List problem solution 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
Solution in C Programming
struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode *list1 = NULL;
struct ListNode *list2 = NULL;
struct ListNode *p = NULL;
struct ListNode *q = NULL;
struct ListNode *s = NULL;
struct ListNode *t = NULL;
struct ListNode *tempNew = NULL;
struct ListNode *temp = NULL;
struct ListNode *r = NULL;
p = head;
if(head == NULL)
{
return 0;
}
while(p!=NULL)
{
/* list1 which store the value less than x */
if(p->val < x)
{
temp = (struct ListNode *)malloc(sizeof(struct ListNode));
temp->val = p->val;
temp->next = NULL;
if(list1 == NULL)
{
list1 = temp;
}
else
{
q = list1;
while(q->next!=NULL)
{
q = q->next;
}
q->next = temp;
}
}
/* list2 which store the value greater than equal to x */
else if(p->val >= x)
{
tempNew = (struct ListNode *)malloc(sizeof(struct ListNode));
tempNew->val = p->val;
tempNew->next = NULL;
if(list2 == NULL)
{
list2 = tempNew;
}
else
{
s = list2;
while(s->next!=NULL)
{
s = s->next;
}
s->next = tempNew;
}
}
p = p->next;
}
/* Merging of list1 with list2 */
t = list1;
while(t!=NULL)
{
r = t;
t = t->next;
}
if(list1 == NULL)
{
list1 = list2;
}
else
{
r->next = list2;
}
return list1;
}Solution in C++ Programming
class Solution {
public:
ListNode* partition(ListNode* head, int x) {
ListNode* prev=NULL;
ListNode* sHead=NULL;
ListNode dummy(0);
ListNode *res=&dummy;
while(head!=NULL)
{
if(head->val<x)
{
res->next=head;
if(prev!=NULL)
{
prev->next=head->next;
}
res=res->next;
}
else
{
if(sHead==NULL)
{
sHead=head;
}
prev=head;
}
head=head->next;
}
res->next=sHead;
return dummy.next;
}
};Solution in Java Programming
class Solution {
public ListNode partition(ListNode head, int x) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode prev = dummy;
ListNode node = head;
ListNode pivot = null;
ListNode temp = null;
while (node != null) {
if (node.val < x) {
if (pivot == null) {
prev = node;
node = node.next;
} else {
prev.next = node.next;
node.next = temp.next;
temp.next = node;
node = prev.next;
temp = temp.next;
}
} else {
if (pivot == null) {
pivot = node;
temp = prev;
}
prev = node;
node = node.next;
}
}
return dummy.next;
}
}Solution in Python Programming
class Solution:
def partition(self, head, x):
d1=c1=ListNode(0)
d2=c2=ListNode(0)
while head:
if head.val<x:
c1.next=head
c1=c1.next
else:
c2.next=head
c2=c2.next
head=head.next
c2.next=None
c1.next=d2.next
return d1.nextSolution in C# Programming
/**
* Definition for singly-linked list.
* public class ListNode {
* public int val;
* public ListNode next;
* public ListNode(int val=0, ListNode next=null) {
* this.val = val;
* this.next = next;
* }
* }
*/
public class Solution {
public ListNode Partition(ListNode head, int x)
{
ListNode smallerNodeHead = null;
ListNode currentSmallerNode = null;
ListNode biggerNodeHead = null;
ListNode currentBiggerNode = null;
ListNode currentNode = head;
while (currentNode != null)
{
ListNode temp = currentNode.next;
currentNode.next = null;
if (currentNode.val < x)
{
if (smallerNodeHead == null)
{
smallerNodeHead = currentNode;
currentSmallerNode = currentNode;
}
else
{
currentSmallerNode.next = currentNode;
currentSmallerNode = currentSmallerNode.next;
}
}
else
{
if (biggerNodeHead == null)
{
biggerNodeHead = currentNode;
currentBiggerNode = currentNode;
}
else
{
currentBiggerNode.next = currentNode;
currentBiggerNode = currentBiggerNode.next;
}
}
currentNode = temp;
}
if (smallerNodeHead == null || biggerNodeHead == null) return head;
else
{
currentSmallerNode.next = biggerNodeHead;
return smallerNodeHead;
}
}
}Also read,