Arrange the List

CONCEPTS USED:

Basic Pointer Manipulation

DIFFICULTY LEVEL:

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 :

head1 -> first list
head2 -> second list
newHead -> final sorted list

while( list1 is not empty OR list2 is not empty )
    find smaller node out of the list1 and list2
    append this node to the new list
    increment the pointer of the smaller node containing list by 1

if ( list1 becomes empty )
    append all elements of list2 to the new list

if ( list2 becomes empty )
    append all elements of list1 to the new list

return pointer of the new list i.e. newHead

SOLUTIONS:


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

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


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

Node* RearrangeLists(Node* head)
{
  /* if head contains 0 or 1 elements */
  if(head == NULL || head->next == NULL)
    return head;

  Node *temp = head;
  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)
    return head;

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

  /* Now we have two different head */

  Node *p = 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;
    }
  }

  /* Head of the new linked head */
  Node *newHead = sorting;

   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;

  return newHead;
}


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);
            head = CreateNode(head, val) ;
        }

        temp = RearrangeLists(head) ;
            printList(temp);

        printf("\n");
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

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

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

void printList(Node *head) {
    Node *temp = head ;
    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;
      }
    }

    /* Head of the new linked list */
    Node *head = sorting;

     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;

    return head;
}


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;
            head = CreateNode(head, val) ;
        }

        temp =RearrangeLists(head) ;
        if ( temp != NULL )
            printList(temp);
        cout<<endl;
    }
    return 0;
}

import java.io.*;
import java.util.*;
public class Main {
    static class SinglyLinkedListNode {
        public int value;
        public SinglyLinkedListNode next;
        public SinglyLinkedListNode(int nodeData) {
            this.value = nodeData;
            this.next = null;
        }
    }
    static class SinglyLinkedList {
        public SinglyLinkedListNode head;
        public SinglyLinkedListNode tail;

        public SinglyLinkedList() {
            this.head = null;
            this.tail = null;
        }
        public void insertNode(int nodeData) {
            SinglyLinkedListNode node = new SinglyLinkedListNode(nodeData);

            if (this.head == null) {
                this.head = node;
            } else {
                this.tail.next = node;
            }
            this.tail = node;
        }
    }

    static void printLinkedList(SinglyLinkedListNode head) {
        SinglyLinkedListNode temp = head;
        while (temp != null) {
            System.out.print(temp.value + " ");
            temp = temp.next;
        }
    }

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

        SinglyLinkedListNode temp = list;
        SinglyLinkedListNode part = null;
        SinglyLinkedListNode partition = null;

        /* 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 */

        SinglyLinkedListNode p = list; 
        SinglyLinkedListNode q = partition;

        SinglyLinkedListNode sorting = null;

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

        /* Head of the new linked list */
        SinglyLinkedListNode head = sorting;

        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;

        return head;
    }


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

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

        int testCases = scanner.nextInt();
        while (testCases-- > 0) {
            SinglyLinkedList llist = new SinglyLinkedList();
            int size = scanner.nextInt();
            for (int i = 0; i < size; i++) {
                int val = scanner.nextInt();
                llist.insertNode(val);
            }
            SinglyLinkedListNode temp = RearrangeLists(llist.head);
            printLinkedList(temp);
            System.out.print("\n");
        }
    }
}

Space Complexity: O(1)

Previous post Arrange the Salary
Next post List Reduction

Leave a Reply

Your email address will not be published. Required fields are marked *