Merging two Sorted Circular Singly Linked Lists

1
votes

I am practicing some algorithm problems before an exam in a C language course and and I got stuck (for at least 3 or even 4 hours) at this question which I don't know how to answer:

You have two circular singly linked lists that are already sorted, you have to merge them and return the head of the new circular linked list without creating any new extra nodes. The returned list should be sorted as well.

The node structure is:

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

I tried many ways (recursive and non recursive) but none solved the problem.

Thanks for any help.

4
calgorithmsingly-linked-listcircular-list
Are you familiar with merge sort? This is basically the merge step, and it can be done in-place in a linked list. - amit
You can break the two lists at the end node ( you know its the last because the next node has a smaller values) Now question reduces to merging to linked lists in place which is easy to do. After they are merged again make it cyclic by pointing last next to first element - sashas
You should show what you consider to be your best attempt. There's no real need for a recursive algorithm, though it can certainly be written recursively if you prefer. What's causing you to stumble? Is it the circular linked lists? - Jonathan Leffler
@sasha This logic fails for a linked list with all elements with the same value (1->1->1->1->...->1 is a valid sorted linked list). You need to mark the head and end the merge when reaching it. - amit
@Saita as amit said take care of the case if all elements are the same . You can do that by choosing any element as head , noting down its value and traversing the list until you meet a different value or end up again at the head. If you end up again at the head all values are same. - sashas

4 Answers

2
votes

This is basically the merge step from merge sort.

In a linked list, it can be done in place.

The idea is to have an iterator for each list, and until the data in the merged list is exhausted, compare node from list1 to node from list2, if list2_iterator

Inserting a node before the current node is done by maintaining an extra prev iterator.

Note that in the entire process of this algorithm - not a single new node was created, all you did was "move" nodes from list2 to list1.

Complexity if this procedure is O(n).

1
votes

Maintain a queue with two linked list firstly.Following is the pseudo code for it:-

 queue* merge_queues (queue* first, queue* second)
       {

           queue* merged_queue = create_queue(first->capacity + second->capacity);
           if (first != NULL && second != NULL){
              while ( !is_empty (first) && !is_empty (second)){
           int max;
           if ( peekqueue (first) > peekqueue (second)){
               max = peekqueue (first);
               dequeue (first);
           }
           else{
                max = peekqueue (second);
                dequeue (second);
           }
           enqueue( merged_queue, max);
        }
         while ( !is_empty (first)){
              enqueue( merged_queue, peekqueue(first));
              dequeue (first);
         }
         while (!is_empty (second)){
             enqueue (merged_queue, peekqueue(second));
             dequeue (second);
        }
    }
    return merged_queue;
}
0
votes

Example code to merge two already sorted lists. To check for the end node of a circular list, check for pointer to head node of list instead of NULL, and after reaching the end of one list you'll need to link the remaining nodes one at a time from the other list since the terminator isn't NULL. After the merge, you'll need to set the last node's next pointer to the head node to make it a circular list. The code checks for Src2 < Src1 to be similar to C++ standard library sort compares which use < and not <=.

NODE * MergeLists(NODE *pSrc1, NODE *pSrc2)
{
NODE *pDst = NULL;                      /* destination head ptr */
NODE **ppDst = &pDst;                   /* ptr to head or prev->next */
    while(1){
        if(pSrc1 == NULL){              /* if end of Src1 */
            *ppDst = pSrc2;             /*   append remainder of Src2 */
            break;                      /*   and break out of loop */
        }
        if(pSrc2 == NULL){              /* if end of Src2 */
            *ppDst = pSrc1;             /*   append remainder of Src1 */
            break;                      /*   and break out of loop */
        }
        if(pSrc2->data < pSrc1->data){  /* if Src2 < Src1 */
            *ppDst = pSrc2;             /*   append node from Src2 */
            pSrc2 = *(ppDst = &(pSrc2->next));
            continue;
        } else {                        /* else Src1 <= Src2 */
            *ppDst = pSrc1;             /*   append node from Src1 */
            pSrc1 = *(ppDst = &(pSrc1->next));
            continue;
        }
    }
    return pDst;
}
0
votes

This merges two cyclic linked list. The code assumes both lists are already sorted and start a the correct point.

#include <stdio.h>

struct llist {
        struct llist *next;
        int value;
        };

struct llist wheel[] =
{{ wheel+1, 0 }
,{ wheel+2, 2 }
,{ wheel+3, 4 }
,{ wheel+0, 6 }
};
struct llist cycle[] =
{{ cycle+1, 0 }
,{ cycle+2, 3 }
,{ cycle+3, 6 }
,{ cycle+0, 9 }
};

struct llist *mergelists(struct llist *one, struct llist *two)
{
struct llist *einz, *zwei;
struct llist *result ,**pp;

if (!one) return two;
if (!two) return one;

result = NULL; pp= &result;

for (einz=one, zwei=two; einz || zwei; pp = &(*pp)->next ) {
        if ( !zwei || einz && einz->value <= zwei->value) {
                *pp = einz; einz = einz->next == one ? NULL : einz->next;
                }
        else    {
                *pp = zwei; zwei = zwei->next == two ? NULL : zwei->next;
                }
        }
*pp = result; /* close the loop */
return result;
}

int main(void)
{
struct llist *p;

        /* This loops.  forever ... */
for(p = mergelists( wheel, cycle); p ; p = p->next) {
        printf("%p = %d\n", (void*) p, p->value );
        }
return 0;
}