{"id":2026,"date":"2020-07-01T09:51:30","date_gmt":"2020-07-01T09:51:30","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2026"},"modified":"2022-05-23T11:16:33","modified_gmt":"2022-05-23T11:16:33","slug":"arrange-the-list","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/arrange-the-list\/","title":{"rendered":"Arrange the List"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Basic Pointer Manipulation<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Medium <\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

Given a linked list of N<\/code> 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.<\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example:<\/h4>\n
Input : 3 -> 4 -> 6 -> 7 -> 8 -> 2 -> 3 -> 4\n\nOutput : 2 -> 3 -> 3 -> 4 -> 4 -> 6 -> 7 -> 8\n\nExplanation : 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.<\/code><\/pre>\n
OBSERVATION :<\/h3>\n
\n
The problem can be seen as merging two sorted linked list in-place i.e. without using any extra space.<\/p>\n<\/blockquote>\n
SOLVING APPROACH:<\/h3>\n
\n
    \n
  1. \n
    We already have the head<\/code> of our first list as the head<\/code> of our original list, now we need to learn online programming courses<\/a> to find the head<\/code> of the second list, this can be easily done by traversing the list and checking wherever the ith<\/sup><\/code> node value becomes greater than the (i+1)th<\/sup><\/code> node value. Then (i+1)th<\/sup><\/code> node is our head<\/code> pointer for the second list.<\/p>\n<\/li>\n
  2. \n
    Now create a new newHead<\/code> that will point to our newly created list.<\/p>\n<\/li>\n
  3. \n
    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.<\/p>\n<\/li>\n
  4. \n
    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.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    ALGORITHM :<\/h3>\n
    <\/p>\n
    SOLUTIONS:<\/h3>\n
    \t\t\t\t\t\t