  Get free ebooK with 50 must do coding Question for Product Based Companies solved
Fill the details & get ebook over email  Thank You!
We have sent the Ebook on 50 Must Do Coding Questions for Product Based Companies Solved over your email. All the best!

# Arrange the List ### CONCEPTS USED:

Basic Pointer Manipulation

Medium

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given a linked list of `N` nodes such that the list is sorted in two parts, the first part and second part are sorted in increasing order independently. Your task is to arrange the linked list in sorted manner.

See original problem statement here

#### For Example:

``````Input : 3 -> 4 -> 6 -> 7 -> 8 -> 2 -> 3 -> 4

Output : 2 -> 3 -> 3 -> 4 -> 4 -> 6 -> 7 -> 8

Explanation : 3 -> 4 -> 6 -> 7 -> 8 and 2 -> 3 -> 4 were separately sorted two list which we have combined to form a single sorted list as 2 -> 3 -> 3 -> 4 -> 4 -> 6 -> 7 -> 8.``````

### OBSERVATION :

The problem can be seen as merging two sorted linked list in-place i.e. without using any extra space.

### SOLVING APPROACH:

1. We already have the `head` of our first list as the `head` of our original list, now we need to learn online programming courses to find the `head` of the second list, this can be easily done by traversing the list and checking wherever the `ith` node value becomes greater than the `(i+1)th` node value. Then `(i+1)th` node is our `head` pointer for the second list.

2. Now create a new `newHead` that will point to our newly created list.

3. Now Keep traversing the former two lists simultaneously, and appending the smaller node out of the two in the new list. Also increment the pointer of the smaller node to point to the next node.

4. In this way all the elements from both the list will be appended to the new list. Keep doing this process till any of the list becomes empty, then append all the remaining nodes to the new list.

### ALGORITHM : ### SOLUTIONS:

```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct Node
{
int value;
struct Node* next;
}Node;

{
Node *newnode = (struct Node*)malloc(sizeof(struct Node));
newnode->value = val ;
newnode->next = NULL ;
static Node *temp;
if ( head == NULL ) {
}
else
{
temp->next = newnode ;
temp =temp->next;
}
}

if (temp) {
while ( temp!= NULL ) {
printf ( "%d ", temp->value ) ;
temp = temp->next ;
}
}
}

{
/* if head contains 0 or 1 elements */

Node *part = NULL;
Node *partition = NULL;

/* findint the point of partition between two head */
while(temp->next != NULL){
if(temp->value > temp->next->value){
part = temp;
partition = temp->next;
break;
}
temp = temp->next;
}

/* if there exits no partition */
if(partition == NULL)

/* set last element of head 1 to point to NULL */
part->next = NULL;

/* Now we have two different head */

Node *q = partition;

Node *sorting = NULL;

if(p != NULL && q != NULL){
if(p->value < q->value){
sorting = p;
p = p->next;
}
else{
sorting = q;
q = q->next;
}
}

while(p != NULL && q != NULL){
if(p->value < q->value){
sorting->next = p;
sorting = p;
p = p->next;
}
else{
sorting->next = q;
sorting = q;
q = q->next;
}
}

if(p == NULL) sorting->next = q;
if(q == NULL) sorting->next = p;

}

int main() {

int t;
scanf("%d", &t);
while(t--){

Node *head = NULL, *temp ;
int size,val;
scanf("%d", &size);
for ( int i = 0 ; i < size ; i ++ ) {
scanf("%d", &val);
}

printList(temp);

printf("\n");
}
return 0;
}
```
```
#include <bits/stdc++.h>
using namespace std;

typedef struct Node
{
int data;
struct Node* next;
}Node;

{
Node *newnode = new Node;
newnode->data = val ;
newnode->next = NULL ;
static Node *temp;
if ( head == NULL ) {
}
else
{
temp->next = newnode ;
temp =temp->next;
}
}

if (temp) {
while ( temp!= NULL ) {
cout<<temp->data<<" ";
temp = temp->next ;
}
}
}

Node* RearrangeLists(Node* list)
{
if(list == NULL || list->next == NULL)
return list;

Node *temp = list;

Node *part = NULL;
Node *partition = NULL;
int f = 0;

/* findint the point of partition between two list */
while(temp->next != NULL){
if(temp->data > temp->next->data){
part = temp;
partition = temp->next;
break;
}
temp = temp->next;
}

/* if there exits no partition */
if(partition == NULL)
return list;

/* set last element of list 1 to point to NULL */
part->next = NULL;

/* Now we have two different list */

Node *p = list;
Node *q = partition;

Node *sorting = NULL;

if(p != NULL && q != NULL){
if(p->data < q->data){
sorting = p;
p = p->next;
}
else{
sorting = q;
q = q->next;
}
}

while(p != NULL && q != NULL){
if(p->data < q->data){
sorting->next = p;
sorting = p;
p = p->next;
}
else{
sorting->next = q;
sorting = q;
q = q->next;
}
}

if(p == NULL) sorting->next = q;
if(q == NULL) sorting->next = p;

}

int main() {

int t;
cin>>t;
while(t--){

Node *head = NULL, *temp ;
int size,val;
cin>>size;
for ( int i = 0 ; i < size ; i ++ ) {
cin>>val;
}

if ( temp != NULL )
printList(temp);
cout<<endl;
}
return 0;
}
```
```import java.io.*;
import java.util.*;
public class Main {
public int value;
this.value = nodeData;
this.next = null;
}
}

this.tail = null;
}
public void insertNode(int nodeData) {

} else {
this.tail.next = node;
}
this.tail = node;
}
}

while (temp != null) {
System.out.print(temp.value + " ");
temp = temp.next;
}
}

{
/* if list contains 0 or 1 elements */
if(list == null || list.next == null)
return list;

/* findint the point of partition between two list */
while(temp.next != null){
if(temp.value > temp.next.value){
part = temp;
partition = temp.next;
break;
}
temp = temp.next;
}

/* if there exits no partition */
if(partition == null)
return list;

/* set last element of list 1 to point to null */
part.next = null;

/* Now we have two different list */

if(p != null && q != null){
if(p.value < q.value){
sorting = p;
p = p.next;
}
else{
sorting = q;
q = q.next;
}
}

while(p != null && q != null){
if(p.value < q.value){
sorting.next = p;
sorting = p;
p = p.next;
}
else{
sorting.next = q;
sorting = q;
q = q.next;
}
}

if(p == null) sorting.next = q;
if(q == null) sorting.next = p;

}

private static final Scanner scanner = new Scanner(System.in);

public static void main(String[] args) throws IOException {

int testCases = scanner.nextInt();
while (testCases-- > 0) {
int size = scanner.nextInt();
for (int i = 0; i < size; i++) {
int val = scanner.nextInt();
llist.insertNode(val);
}
System.out.print("\n");
}
}
}
```

Space Complexity: `O(1)`

[forminator_quiz id=”2133″]

This article tried to discuss Basic Pointer Manipulation. Hope this blog helps you understand and solve the problem. To practice more problems on Basic Pointer Manipulation you can check out MYCODE | Competitive Programming.