Merging two sorted linked lists

Question

This is one of the programming questions asked during written test from Microsoft. I am giving the question and the answer that I came up with. Thing is my answer although looks comprehensive (at least to me), I feel that the number of lines can be reduced. It was asked in C and I am a Java person but I managed to code it (my answer may contain too many Java like syntaxes)

Ok, here is the question.

You have two lists that are already sorted, you have to merge them and return a new list without any new extra nodes. The returned list should be sorted as well.

The method signature is,

Node* MergeLists(Node* list1, Node* list2);

struct Node{
    int data;
    Node *next;
}

The following is the solution I came up with,

Node* MergeLists(Node* list1, Node* list2){
    Node* mergedList;
    if(list1 == null && list2 ==null){//if both are null, return null
        return null;
    }
    if(list1 == null){//if list1 is null, simply return list2
        return list2;
    }
    if(list2 == null){//if list2 is null, simply return list1
        return list1;
    }
    if(list1.data < list2.data){//initialize mergedList pointer to list1 if list1's data is lesser
        mergedList = list1;
    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList = list2;
    }
    while(list1!=null && list2!=null){
        if(list1.data < list2.data){
            mergedList->next = list1;
            list1 = list1->next;
        }else{
            mergedList->next = list2;
            list2 = list2->next;
        }
    }
    if(list1 == null){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
        mergedList->next = list2;
    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
        mergedList->next = list1;
    }
    return mergedList;
}

I am very confident this can be enhanced. Please help me find what lines are redundantly I've added. Please feel free to criticize my syntax errors and logic.

Thanks!

Travers

Some of your code can be shortened simply by using trinary operators in the start. I.E rewrite the parameter tests using to mergedList = (list1 == null ? list2 : null) and save lines of code, though 'not' operations. – Wilbertwilborn

Bragboy, do you mind changing your title into a more descriptive form like "Merging two sorted lists"? Your current title (Need your advise/tips on this coding problem) is what we are all here for. :) It does not identify or promote your question. – Rinarinaldi

Answer 1

Your code is overloaded with if-s inserted for handling "special" cases, which bloats it a lot and makes it difficult to read. This usually happens when you decide to handle special cases "by code" instead of finding a way to handle them "by data". A statement attributed to David Wheeler says "All problems in computer science can be solved by another level of indirection". That "extra level of indirection" usually works very well with lists, helping to significantly reduce clutter created by those ifs.

To illustrate the above, here's what my code would look like

#define SWAP_PTRS(a, b) do { void *t = (a); (a) = (b); (b) = t; } while (0)

Node* MergeLists(Node* list1, Node* list2) 
{
  Node *list = NULL, **pnext = &list;

  if (list2 == NULL)
    return list1;

  while (list1 != NULL)
  {
    if (list1->data > list2->data)
      SWAP_PTRS(list1, list2);

    *pnext = list1;
    pnext = &list1->next;
    list1 = *pnext;
  }

  *pnext = list2;
  return list;
}

Some might argue that the use of an extra level of indirection in pnext pointer actually makes the code more difficult to read. I'd agree that for a newbie the approach might pose some difficulties, but for an experienced programmer this should be easily digestible as an idiom.

Obsequies

Thanks. Will consider this kind of approach in attacking problems of this nature in future. That really helped! – Travers

Wouldn't this attempt to dereference null when null is passed for list2? – Albumose

@meriton: Yes, it would. I added an extra check :) Thank you. – Obsequies

+1 for explanation about indirection and simplifying the while condition to only check the modified pointer. – Albumose

@polygenelubricants: A typo. The intent was to return list1 (not list) when list2 is null. Fixed. – Obsequies

why not change these 2 lines :pnext = &list1->next; list1 = *pnext; to list1= list1->next; ? – Impious

@Josh Morrison: Er... Because that simply wouldn't work. It is important to maintain the correct value of pnext at all times. The previous line *pnext = list1 relies on it. – Obsequies

Answer 2

The most glaring bug is in your loop, you keep overwriting mergedList->next, losing the previously added node. That is, your returned list will never contain more than two nodes, regardless of input ...

It's been a while since I did C, but I would do it as follows:

Node* merge(Node* list1, Node* list2) {
    Node* merged = null;
    Node** tail = &merged;

    while (list1 && list2) {
        if (list1->data < list2->data) {
            *tail = list1;
            list1 = list1->next;
        } else {
            *tail = list2;
            list2 = list2->next;
        }
        tail = &((*tail)->next);
    }
    *tail = list1 ? list1 : list2;
    return merged;
}

Albumose

Man! Thats a BIG HOLE!. i really did not notice that. – Travers

Answer 3

My take, with a test case

So far all of the answers have been interesting and well done. It's possible that this one is more like what an interviewer would like to see, featuring DRY/DIE, and TDD. :-)

#include <stdio.h>

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

Node l1[] = {
  { 1, &l1[1] },
  { 3, &l1[2] },
  { 5, &l1[3] },
  { 7, &l1[4] },
  { 9, &l1[5] },
  {11, 0 },
};

Node l2[] = {
  { 2, &l2[1] },
  { 4, &l2[2] },
  { 6, 0 },
};

Node* MergeLists(Node* list1, Node* list2) {
  Node *t, **xt;
  for(xt = &t; list1 || list2;) {
    Node **z = list1 == NULL ? &list2 :
               list2 == NULL ? &list1 :
               list1->data < list2->data ? &list1 : &list2;
    *xt = *z;
     xt = &(*z)->next;
    *z  = *xt;
  }
  *xt = NULL;
  return t;
}

int main(void) {
  for(Node *t = MergeLists(l1, l2); t; t = t->next) 
    printf("%d\n", t->data);
  return 0;
}

Adamik

That is an ingenious way of constructing a linked list. Love it. – Realism

Answer 4

It doesn't get any more elegant than this:

Node* merge2(Node* n1, Node* n2) {
    n1->next = merge(n1->next, n2);
    return n1;
}

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
           (n1->data < n2->data) ?
               merge2(n1, n2) :
               merge2(n2, n1);
}

Assuming that you understand recursion, this is as clear as it gets.

---

I should point out that this is good for an interview answer only (where presumably demonstrating clarity of thought has more impact than simply showing that you know how to write programs). In practice, you wouldn't want to merge this way, since it uses O(n) stack depth, which likely would cause a stack overflow. Also, it's not a tail-recursion, so it's not compiler-optimizable.

Realism

Well, it's concise, but I wouldn't call nested ternaries "clear." – Known

Well, it takes getting used to, but unless you abuse it, nested ternaries actually makes for a very clear code to me at least. It requires good logic and good formatting, some parentheses and some indentation, but that's about it. – Realism

i find it really hard to write a recursive method without the help of a IDE. I always want to do a test or two before actually finalizing on one. Thats the reason I try to avoid it as much as possible – Travers

It is "elegant" in a sense that it uses recursion. But from the functional point of view, using recursion in a straightforwardly cyclical situation is not exactly an example of functional elegance. Any cycle can be replaced with recursion. But should it be? – Obsequies

It does make for nice code and as long as the final operation is the return, compilers can make it just as efficient as a loop. I'd say I like it. – Parthinia

I admit that this is not "practical", since the O(n) recursion depth would cause stack overflow, etc. As an interview answer, though, this shows that you really know your computation theory. – Realism

If I were you, I would resist the need to create an extra function :) You could've easily done it with one function by using , operator. The last branch would simply look as n1->data < n2->data ? n1->next = merge(n1->next, n2), n1 : n2->next = merge(n2->next, n1), n2. But that starts to smell of Obfuscated C Code Contest :) – Obsequies

Yes, the contrast between your solution and mine is that yours (after all the bugs are fixed) shows that the author knows how to write correct code. Mine shows that the author knows how to think clearly. – Realism

Answer 5

Divide et Impera

(i.e. MergeSort)

Ritter

This is exactly the correct answer, why the downvotes? @Luca: +1 from me. – Damal

@tzaman: How on world is this a related answer to this question? – Travers

@Bragaadeesh: Do you have to sort? I wonder why not use well known algorithms. Surely you get best performances using Divide & Impera pattern, instead of simply iterating over the two lists. It is just a critics about the algorithm pattern, indeed it seems to me pertinent. – Ritter

I voted you up as well. This is exactly the merge part of mergesort. – Jiles

Aw!! Come on guys, please read the question fully. This is not about sorting algorithm. The data is already sorted. This question is more about programming style. – Travers

It's about merging two sorted lists. The second part of merge sort is merging two sorted lists. It's pretty straight forward. – Abscissa

Answer 6

So merging polygen wit AndreyT we get:

Node* merge(Node* n1, Node* n2) {
    return (n1 == null) ? n2 :
           (n2 == null) ? n1 :
             (n1->data < n2->data) ? 
               (n1->next = merge(n1->next, n2), n1) : 
               (n2->next = merge(n2->next, n1), n2)}

I can't claim credit for this one, but it is the most concise and shows the symmetry between the two arguments, doesn't introduce any obscure helper functions. I am not sure an optimizing compiler will see a tail recursion here but I do. The indentation is a final touch.

Raisin

Answer 7

Use recursion. The code is as follows:

ListNode* mergeTwoSortedLists(ListNode* pHead1, ListNode* pHead2)
{
    if(pHead1 == NULL)
        return pHead2;
    else if(pHead2 == NULL)
        return pHead1;

    ListNode* pMergedHead = NULL;

    if(pHead1->m_nValue < pHead2->m_nValue)
    {
        pMergedHead = pHead1;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1->m_pNext, pHead2);
    }
    else
    {
        pMergedHead = pHead2;
        pMergedHead->m_pNext = mergeTwoSortedLists(pHead1, pHead2->m_pNext);
    }

    return pMergedHead;
}

Avery

Answer 8

My Golang solution for this Problem:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    head1 := list1
    head2 := list2
    ans := &ListNode{}
    tail := ans
    for head1 != nil && head2 != nil {
        if head1.Val > head2.Val {
            tail.Next = head2
            head2 = head2.Next
            tail = tail.Next
        } else {
            tail.Next = head1
            head1 = head1.Next
            tail = tail.Next
        }
    }

    if head1 != nil {
        tail.Next = head1
    }
    if head2 != nil {
        tail.Next = head2
    }
    return ans.Next
}

Given list: list1 = 1->2->3 list2 = 1->2->4->5

Output: 1->1->2->2->3->4->5

Define an empty list and push the element at the last if any of the below conditions satisfy.

At the end return ans.next which will be the current head of the newly created list.

Fascist

Answer 9

public void Merge(LinkList list1, LinkList list2) {
        if (list1.head == null && list2.head == null) {
            System.out.println("Empty list"); //Check if lists are empty
        }
        if (list1.head == null) { //If list1 is empty print list2
            list2.printList();
        }
        if (list2.head == null) { //If list2 is empty print list1
            list1.printList(); 
        }
        LinkList list3 = new LinkList(); //create a new LinkList object for merging
        Node a = list1.head; //Beginning of list1
        Node b = list2.head; //Beginning of list2
        while (a != null && b != null) { //Until list ends
            if (a.value <= b.value) { //Compare values of list1 against list2
                list3.insert(a.value); //Insert values to new list
                a = a.next;
            } else if (a.value >= b.value) {
                list3.insert(b.value);
                b = b.next;
            }  else if (a.value == b.value){ //Insert only unique values and discard repeated values
            list3.insert(a.value);
            a = a.next;
            b = b.next;
        }
        }
        if (a == null) {
            while (b != null) {
                list3.insert(b.value); //If list1 becomes empty, attach rest of the list2 to list3
                b = b.next;
            }
        }
        if (b == null) {
            while (a != null) {
                list3.insert(a.value);
                a = a.next;
            }
        }
        list3.printList(); //print merged list
    }
}

Hi guys ! I was preparing for an interview this month and while I was working on this problem, this is the solution I came up with. I compared my solution with many solutions you posted here and find my program extremely lengthy. Although I find this easier to understand and implement, is there a better solution in Java to the existing code. I'm looking for a better time complexity solution. Any help/direction/tip is appreciated.

PS: I was unable to come up with a Java solution for the programs listed above in C which used pointers.

Ceylon

Answer 10

This is my take. Unlike other solutions it identifies and skips over consecutive nodes on one list which are smaller or equal to the head node of the other list. The head of the other list is attached at the end of such sequence and the process is repeated after switching roles. This approach minimizes the number of assignments to Node.next while limiting NULL testing to single check in each iteration.

Node * merge(Node *list1, Node *list2)
{
    if (!list1) return list2;
    if (!list2) return list1;

    Node *tmp;

    // compare head nodes and swap lists to guarantee list1 has the smallest node
    if (list1->val > list2->val) {
        tmp = list2;
        list2 = list1;
        list1 = tmp;
    }

    Node *tail = list1;

    do {
        // Advance the tail pointer skipping over all the elements in the result
        // which have smaller or equal value than the first node on list2
        while (tail->next && (tail->next->val <= list2->val)) {
            tail = tail->next;
        }
        // concat list2 at tail of result and make the rest after tail list2 
        tmp = tail->next;
        tail->next = list2;
        tail = list2;
        list2 = tmp;
    } while (list2);

    return list1;
}

Claybourne

Answer 11

#include<stdio.h>

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

NODE * func(NODE*,NODE*);
int main()
{
    int i;
    int size;
    int value;
    NODE * head1,*head2,*newNode,*ptr,*final;
    printf("\nPlease enter the number of elements\n");
    scanf("%d",&size);

    for(i=0;i<size;i++)
    {
            printf("List 1\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head1=newNode;
                ptr=newNode;

            }
    }
    for(i=0;i<size;i++)
    {
            printf("\n\nList 2\n");
            printf("Please enter the value number %d \n",i+1);
            scanf("%d",&value);
            newNode=(NODE*)malloc(sizeof(NODE));
            newNode->data=value;
            newNode->next=NULL;
            if(i!=0)
            {
                ptr->next=newNode;  
                ptr=ptr->next;
            }

            if(i==0)
            {
                head2=newNode;
                ptr=newNode;

            }
    }

    final=func(head1,head2);
    printf("\n\n");
    while (final!=NULL)
    {
        printf("%d -->",final->data);
        final=final->next;
    }
    printf("NULL
    ");
    return 0;
}

NODE* func(NODE* list1, NODE* list2)
{

    NODE* mergedList,*mergeHead=NULL;
    if(list1 == NULL && list2 ==NULL){//if both are NULL, return NULL
        return NULL;
    }
    if(list1 == NULL){//if list1 is NULL, simply return list2
        return list2;
    }
    if(list2 == NULL){//if list2 is NULL, simply return list1
        return list1;
    }
    mergedList = (NODE*)malloc(sizeof(NODE));
    if(list1->data < list2->data){//initialize mergedList pointer to list1 if list1's data is lesser

        mergedList->data=list1->data;
        mergedList->next=NULL;
        list1 = list1->next;

    }else{//initialize mergedList pointer to list2 if list2's data is lesser or equal
        mergedList->data=list2->data;
        mergedList->next=NULL;
        list2 = list2->next;

    }
    mergeHead=mergedList;

    while(list1!=NULL && list2!=NULL){
        if(list1->data < list2->data){
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
        }else{
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
        }
    }
    if(list1 == NULL){//remaining nodes of list2 appended to mergedList when list1 has reached its end.
       while(list2!=NULL)
       {
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list2->data;
            mergedList->next=NULL;
            list2 = list2->next;
       }

    }else{//remaining nodes of list1 appended to mergedList when list2 has reached its end
            mergedList->next = (NODE*)malloc(sizeof(NODE));
            mergedList=mergedList->next;
            mergedList->data=list1->data;
            mergedList->next=NULL;
            list1 = list1->next;
    }
    return mergeHead;
}

Foist

Answer 12

I have created recursion function for it. Here is my solution:

Node* merge_recursion(Node* l1, Node* l2)
{
        if (!l1)
                return l2;
        if (!l2)
                return l1;

        if (l1->data < l2->data) {
                l1->next = merge_recursion(l1->next, l2);
                return l1;
        } else {
                l2->next = merge_recursion(l1, l2->next);
                return l2;
        }
}

Store return pointer into new pointer variable (in main() / calling function) and traverse linked list on new pointer to print data, it will result sorted merged linked list.

Kokoschka

Answer 13

You can use recursion:

Node* MergeLists(Node *headA, Node* headB)
{

if(headA==NULL){
    return headB;
}else if(headB ==NULL){
    return headA;
}
Node* head = NULL;
if(headA->data <= headB->data){
    head= headA;
    head->next = MergeLists(headA->next,headB);
}else{
    head= headB;
    head->next = MergeLists(headA,headB->next);
}
 return head;
}

Gussy

… and O(n) memory. – Yellows

Answer 14

You may use Java 8, Stream API to merge, get Distinct and sort. Below is sample code for sorting and merging two list with Integer elements

List<Integer> list1= Arrays.asList(2,3,5,8);
List<Integer> list2 = Arrays.asList(3,6,8);

List<Integer> finalList = new ArrayList<>();
finalList.addAll(list1);
finalList.addAll(list2);

List<Integer>  mergeSortedList = 
  finalList.stream()
    .distinct()
    .sorted()
    .collect(Collectors.toList());
System.out.println(mergeSortedList);

Palmira

Please asses the asymptotic run time complexity of this approach. – Yellows

The question was supposed to be in C, yet you give a - not quite that clever - answer in Java. – Evers

question was [tagged] C, yet you give [an] answer in Java not a first – Yellows

Answer 15

Iterative solution for merging two sorted Linked List:

class ListNode:
    def __init__(self, val=0, next=None):

         self.val = val

         self.next = next


    class Solution:
            def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
                head = ListNode(-200)
                prev = head
                while l1 and l2:
                    if l1.val <=l2.val:
                        prev.next = l1
                        l1 = l1.next
                    else:
                        prev.next = l2
                        l2 = l2.next
                    prev = prev.next
                    
                prev.next = l1 if l1 is not None else l2
                
                return head.next
                

Haakon

Answer 16

This is solution on JAVA and it works.. where,

public class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}    





 public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
                
                if(list1 == null) return list2;
                if(list2 == null) return list1;
                  
                if(list1.val < list2.val) 
                {
                    list1.next = mergeTwoLists(list1.next, list2);
                    return list1;
                }
                else 
                {
                    list2.next = mergeTwoLists(list1, list2.next);
                    return list2;
                }
                  
            }

Changeup

OP is looking for an answer in C, not java – Uncork

Answer 17

Here I have the whole code for merging two sorted linked list with all the possible cases.

I have taken two pointers head and tail to point towards the final sorted list and there is no new linked list the is being created, head1 and head2 are the head pointers of the linked lists that are given to the merging functions as input.

And the two linked lists are also taken from the user as input with the help of takeInput function and the list is printed using the print function

#include<iostream>
using namespace std;

//this is the creation of node class which is used to create a node of the linked list
class Node
{
    public:
        int data;
        Node * next;
        
    Node(int data)
    {
        this -> data = data;
        next = NULL;
    }
};

//this is the creation of linked list 
//-1 is used as the termimator or to stop taking input
Node * takeInput()
{
    int data;
    cout<<"Enter the data of the node to be inserted (use -1 as the terminator) : ";
    cin>>data;
    Node * head = NULL;
    Node * tail = NULL;
    
    while(data != -1)
    {
        Node * newNode = new Node(data);
        if(head == NULL)
        {
            head = newNode;
            tail = newNode;
        }
        else
        {
            tail -> next = newNode;
            tail = tail -> next;
        }
        cout<<"Enter the data of the node to be inserted (use -1 as the terminator) : ";
        cin>>data;
    }
    return head;
}

//this is the function that helps in printing the linked list
void printLinkedList(Node * head)
{
    if(head == NULL)
    {
        return;
    }
    Node * temp = head;
    while(temp != NULL)
    {
        cout<<temp -> data<<" ";
        temp = temp -> next;
    }
    cout<<endl;
}

//this is the function where two sorted ascending ordered linked list are merged    
Node * mergeSortedLinkedList(Node * head1 , Node * head2)
{
    Node * head = NULL;  //head of the merged linked list
    Node * tail = NULL;  //tail of the merged linked list
    if(head1 == NULL && head2 == NULL) //condition when both the linked list are empty
    {
        cout<<"cannot merge empty linked list ! "<<endl;
        return head;
    }
    if(head1 == NULL and head2 != NULL) //condition when first linked list is empty
    {
        head = head2;
        return head;
    }
    if(head2 == NULL and head1 != NULL) //condition when second linked list is empty
    {
        head = head1;
        return head;
    }
    if(head1->data < head2-> data) //for the first iteration to assign the merged linked list head and tail
        {
            head = head1;
            tail = head1;
            head1 = head1 -> next;
        }
        else
        {
            head = head2;
            tail = head2;
            head2 = head2 -> next;
        }
    while(head1 != NULL and head2 != NULL) //from here it takes care of the whole processes
    {
        if(head1->data <= head2-> data)
        {
            tail -> next = head1;
            tail = tail -> next;
            head1 = head1 -> next;
        }
        else
        {
            tail -> next = head2;
            tail = tail -> next;
            head2 = head2 -> next;
        }
    }
    if(head1 == NULL) //if 1st linked list is smaller than the second linked list
    {
        tail -> next = head2;
    }
    if(head2 == NULL) //if 2nd linked list is smaller than the first linked list
    {
        tail -> next = head1;
    }
    return head;
}

//this is the main from where all the functions are called accordingly
int main()
{
    cout<<"Enter the data of the first linked list ! (make sure its sorted and is in ascending order) "<<endl;
    Node * head1 = takeInput();
    cout<<"The first Linked List is : "; 
    printLinkedList(head1);
    cout<<endl<<"********************************************************************************************"<<endl;
    cout<<"********************************************************************************************"<<endl;
    cout<<"Enter the data of the second linked list ! (make sure its sorted and is in ascending order) "<<endl;
    Node * head2 = takeInput();
    cout<<"The second Liked list is : ";
    printLinkedList(head2);
    cout<<endl<<"********************************************************************************************"<<endl;
    cout<<"********************************************************************************************"<<endl;
    Node * head = mergeSortedLinkedList(head1, head2);
    cout<<"The resulting sorted linked list is : ";
    printLinkedList(head);
    cout<<endl<<"--------------------------------------------------------------------------------------------"<<endl;
    cout<<"--------------------------------------------------------------------------------------------"<<endl;
}

Entrain

Answer 18

#include <stdio.h>
#include <stdlib.h>

// Definition of the linked list node structure

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

// Function prototypes

Node* createSortedList(void);
Node* insertIn(Node* start, int data);
void displayList(const Node* start);
Node* mergeLists(Node* list1, Node* list2);

int main() {
    Node *list1 = NULL, *list2 = NULL, *mergedList = NULL;

    // Create the first sorted list

    printf("Create first sorted list:\n");

    list1 = createSortedList();

    // Create the second sorted list

    printf("Create second sorted list:\n");

    list2 = createSortedList();

    // Display both lists before merging

    printf("List 1: ");

    displayList(list1);

    printf("List 2: ");

    displayList(list2);

    // Merge the lists and remove duplicates
    mergedList = mergeLists(list1, list2);
    printf("Merged List: ");
    displayList(mergedList);

    return 0;
}

/*
 * Function to create a sorted linked list by inserting elements in order
 */
Node* createSortedList(void) {
    Node* start = NULL;
    int n, data;
    printf("Enter the number of nodes: ");
    scanf("%d", &n);

    for (int i = 0; i < n; i++) {
        printf("Enter the element to be inserted: ");
        scanf("%d", &data);
        start = insertIn(start, data);
    }
    return start;
}

/*
 * Function to insert an element in a sorted linked list in order
 */
Node* insertIn(Node* start, nt data) {
    Node *p, *temp;
    temp = (Node*)malloc(sizeof(Node));
    if (!temp) {
        printf("Memory allocation failed\n");
        exit(1);
    }
    temp->data = data;
    temp->next = NULL;

    // If the list is empty or the new node should be the first node
    if (start == NULL || data < start->data) {
        temp->next = start;
        start = temp;
        return start;
    }

    p = start;
    while (p->next != NULL && p->next->data < data) {
        p = p->next;
    }
    temp->next = p->next;
    p->next = temp;
    return start;
}

/*
 * Function to display the elements of the linked list
 */
void displayList(const Node* start) {
    const Node* p = start;
    if (start == NULL) {
        printf("List is empty\n");
        return;
    }
    printf("List: ");
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

/*
 * Function to merge two sorted linked lists into a single sorted linked list without duplicates
 */
Node* mergeLists(Node* list1, Node* list2) {

    Node *mergedList = NULL, **pnext = &mergedList;

//  Initialize with a value that cannot be in the list

    int lastAddedValue = -1; 
    while (list1 != NULL && list2 != NULL) {
        if (list1->data == list2->data) {
            if (list1->data != lastAddedValue) {
                *pnext = (Node*)malloc(sizeof(Node));
                (*pnext)->data = list1->data;
                (*pnext)->next = NULL;
                pnext = &((*pnext)->next);
                lastAddedValue = list1->data;
            }
            list1 = list1->next;
            list2 = list2->next;
        } else if (list1->data < list2->data) {
            if (list1->data != lastAddedValue) {
                *pnext = (Node*)malloc(sizeof(Node));
                (*pnext)->data = list1->data;
                (*pnext)->next = NULL;
                pnext = &((*pnext)->next);
                lastAddedValue = list1->data;
            }
            list1 = list1->next;
        } else {
            if (list2->data != lastAddedValue) {
                *pnext = (Node*)malloc(sizeof(Node));
                (*pnext)->data = list2->data;
                (*pnext)->next = NULL;
                pnext = &((*pnext)->next);
                lastAddedValue = list2->data;
            }
            list2 = list2->next;
        }
    }

    while (list1 != NULL) {
        if (list1->data != lastAddedValue) {
            *pnext = (Node*)malloc(sizeof(Node));
            (*pnext)->data = list1->data;
            (*pnext)->next = NULL;
            pnext = &((*pnext)->next);
            lastAddedValue = list1->data;
        }
        list1 = list1->next;
    }

    while (list2 != NULL) {
        if (list2->data != lastAddedValue) {
            *pnext = (Node*)malloc(sizeof(Node));
            (*pnext)->data = list2->data;
            (*pnext)->next = NULL;
            pnext = &((*pnext)->next);
            lastAddedValue = list2->data;
        }
        list2 = list2->next;
    }

    return mergedList;
}

Fredkin

I would not call this merging lists - it creates & returns a third list containing copies of all elements of the argument list in order. – Yellows

Thank you for contributing to the Stack Overflow community. This may be a correct answer, but it’d be really useful to explain your code further so developers can understand your reasoning. This is especially useful for new developers who aren’t as familiar with the syntax or are struggling to understand the concepts. Would you kindly edit your answer to include additional details to benefit the community? – Silvestro

Your answer could be improved with additional supporting information. Please edit to add further details, such as citations or documentation, so that others can confirm that your answer is correct. You can find more information on how to write good answers in the help center. – Chondriosome

Answer 19

//I have used recursions .
//Sorry for such a long code.
//:) it works,hope it helps.
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node{
    int data;
    struct node *next ;
};
struct node *start1=NULL,*start2=NULL;
struct node*start=NULL;
struct node *create_ll1(struct node *start);
struct node *create_ll2(struct node *start);
void sorted_ll(struct node* node1,struct node* node2);

struct node *display(struct node *start);
void p(struct node*);
main(){
    start1=create_ll1(start1);
    start2=create_ll2(start2);
    //start1=display(start1);
    printf("\n");
    //start2=display(start2);
    sorted_ll(start1,start2);
    //start=display(start);


}
struct node *create_ll1(struct node *start1){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 1: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start1==NULL){
            new_node->next=NULL ;
            start1=new_node;
        }
        else{
            ptr=start1 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start1;

}
struct node *create_ll2(struct node *start2){
    struct node *ptr,*new_node;
    int num;
    printf("Enter -1 for ending \n");
    printf("Enter data for list 2: \n");
    scanf("%d",&num);
    while(num!=-1){
        new_node=(struct node *)malloc(sizeof(struct node));
        new_node->data=num;
        if(start2==NULL){
            new_node->next=NULL ;
            start2=new_node;
        }
        else{
            ptr=start2 ;
            while(ptr->next!=NULL)
            ptr=ptr->next;
            ptr->next=new_node;
            new_node->next=NULL ;
        }
        printf("Enter data: \n");
        scanf("%d",&num);
    }
    return start2;

}

struct node *display(struct node *start){
    struct node *ptr;
    ptr=start;
    while(ptr->next!=NULL){
        printf("\t %d",ptr->data);
        ptr=ptr->next;
    }
        printf("\t %d",ptr->data);
        printf("\n");


    return start ;
}
void sorted_ll(struct node* node1,struct node* node2)
{
    if(!node1){
        p(node2);
        exit(0);
    }
    else if(!node2){
        p(node1);
        exit(0);
    }
    if(node1->data<node2->data){
        printf("%d\t",node1->data);
        sorted_ll(node1->next,node2);


    }
    else{
        printf("%d\t",node2->data);
        sorted_ll(node1,node2->next);
    }
}
void p(struct node* pme){
    while(pme->next!=NULL){
        printf("%d \t",pme->data);
        pme=pme->next;
    }
    printf("%d",pme->data);

}

Pandit

While (sort of) including a comment what all of the code is about is a good start, that comment won't work out of the context of this question. The remainder of your code is uncommented. Once you have a test frame and are confident that your codes works as specified, consider posting on Code Review to live up to your user name. – Yellows