How to merge multiple linked list bundled together in a pointer to pointer into one?-CodePudding

Here I'm experimenting with three linked list (list1, list2, list3), by putting them together in **lists. I'm trying to merge them but how do I even access/navigate through the values inside to start things off?

struct ListNode {
    int val;
    struct ListNode *next;
};

int main() {
    struct ListNode a; struct ListNode b; struct ListNode c;
    a.val = 1; b.val = 4; c.val = 5;
    a.next = &b; b.next = &c; c.next = NULL;
    struct ListNode* list1 = &a;

    struct ListNode d; struct ListNode e; struct ListNode f;
    d.val = 1; e.val = 3; f.val = 4;
    d.next = &e; e.next = &f; f.next = NULL;
    struct ListNode* list2 = &d;

    struct ListNode g; struct ListNode h;
    g.val = 2; h.val = 6;
    g.next = &h; h.next = NULL;
    struct ListNode* list3 = &g;

    list1->next = list2; list2->next = list3; list3->next = NULL;
    struct ListNode** lists = list1;
}

CodePudding user response：

Are you trying to join the three lists serially, such that the last element of list1 points to the first element of list2 and so on?

You can simply do -

// c is the last element of list 1. list2 is already a pointer to a struct ListNode
c.next = list2 // this is exactly equivalent to c.next = &d


// similarly, f is the last element of list 2. list3 is already a pointer to a struct ListNode
f.next = list3 // this is exactly equivalent to f.next = &g

The original lists were

a -> b -> c ->

d -> e -> f ->

g -> h ->

After the above steps, you will have -

a -> b -> c -> d -> e -> f -> g -> h

You're mistake was that you were assuming that list, list2, and list3 refer to the lists as a whole. They are simple pointers to the first elements of each list so -

list1->next = list2

set the next value of the node pointed to by list1 (a) to the address of the first node of list2

You have to find the last element of a list and assign it to the first element of the list you want to merge.

Unless, this is a one-off thing, I would recommend you define a subroutine that takes a pointers to two lists and joins them serially. Something like this -

void joinNodes(ListNode* first, ListNode* second) {
    // loop through first until the last element (say, x) is found
    // set next of x to second
    // end
}

The implementation is left as an exercise for the reader.

CodePudding user response：

FYI : Sometimes a link list class is a different thing than a node on that linked list. Sometimes they are identical classes. In your case you are using a ListNode as both the linklist and the nodes on the linked list.

If you want to append the lists such that you get 1->4->5->1->3->4->2->6-> you would want to implement a helper function that would iterate to the END of the link list and return the last element. It's been a while since I coded any C so expect syntax errors, but something like :

ListNode* getLastNodeFromLinkList(ListNode* n){
    if(n == NULL) return NULL;
    while(n->next != NULL){
        n = n->next;
    }
    return n;
}

Then you can do something like :

struct ListNode* x;
x = getLastNodeFromLinkList(list1);
x->next = list2;
x = getLastNodeFromLinkList(list2);
x->next = list3;