CODEWITHSUNDEEP
cmergelinked-list
DanCode
DanCode

Reputation: 673

C: Merging sorted linked list - move pointers only

I have two sorted linked lists, list1 and list2. My goal is to merge list2 into list1.

The requirements are as follows:

  1. The resulting list should be list1 (no creating a new linked list and having the merged list to be in the new linked list)
  2. The return type must be void
  3. list2 must be empty after the merge
  4. Merged list must be sorted
  5. Cannot delete or remove any nodes. Move pointers only
  6. No recursions
  7. No sorting allowed in the algorithm
  8. No other helper functions

Sample output:

Result:

My code's result is currently

typedef struct listNode {
        char data;
        struct listNode* nextPtr;
} ListNode;
        
typedef ListNode* ListNodePtr;


void mergeSortedList(ListNodePtr list1, ListNodePtr list2) {

    ListNodePtr curr = NULL;
    ListNodePtr last = NULL;

    if (list1->data < list2->data)
    {
        curr = list1;
        last = list1;
        list1 = list1->nextPtr;
    }
    else {
        curr = list2;
        last = list2;
        list2 = list2->nextPtr;
    }
    last->nextPtr = NULL;

    while (list1 != NULL && list2 != NULL) {
        if (list1->data < list2->data) {
            last->nextPtr = list1;
            last = list1;
            list1 = list1->nextPtr;
        }
        else {
            last->nextPtr = list2;
            last = list2;
            list2 = list2->nextPtr;
        }
        last->nextPtr = NULL;
    }

    if (list1 != NULL) {
        last->nextPtr = list1;
    }
    else {
        last->nextPtr = list2;
    }
}

Upvotes: 0

Views: 110

Answers (1)

user9706
user9706

Reputation:

  1. Eliminate ListNodePtr in favor of ListNode * (see Is it a good idea to typedef pointers?).

  2. As @n.m. implied you need to pass in ListNode ** in order to have an effect on caller.

  3. If either list1 or list2 are NULL original code segfaults.

  4. Swap the two lists if *list1 doesn't point to the smallest first node. Then iterate through the two lists using the pointers l1 and l2. The interesting case is moving nodes from l2 to l1. This requires you to look ahead a node on l1m so you can set the inbound pointer to the node being move. Alternatively keep a pointer around to the previous node on l1 than the one we currently looking. Finally, deal with any remaining nodes of l2.

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

typedef struct listNode {
    char data;
    struct listNode* nextPtr;
} ListNode;

ListNode *createList(const char *data) {
    if(!data || !*data) return NULL;
    size_t n = strlen(data);
    ListNode *head = malloc(n * sizeof(*head));
    if(!head) return NULL;
    ListNode *p = head;
    for(size_t i = 0; i < n; i++, p = p->nextPtr) {
        p->data = data[i];
        p->nextPtr = p + 1;
    }
    (p-1)->nextPtr = NULL;
    return head;
}

void mergeSortedList(ListNode **list1, ListNode **list2) {
    if(!*list1 || (*list2 && (*list1)->data > (*list2)->data)) {
        ListNode *tmp = *list1;
        *list1 = *list2;
        *list2 = tmp;
    }
    if(!*list1) return;
    ListNode *l1 = *list1;
    ListNode *l2 = *list2;
    while(l1->nextPtr && l2) {
        if(l1->nextPtr->data <= l2->data)
            l1 = l1->nextPtr;
        else {
            ListNode *tmp = l2->nextPtr;
            l2->nextPtr = l1->nextPtr;
            l1->nextPtr = l2;
            l2 = tmp;
        }
    }
    if(l2) l1->nextPtr = l2;
    *list2 = NULL;
}

void printList(const char *name, ListNode *head) {
    printf("%s: ", name);
    for(; head; head = head->nextPtr) {
        printf("%c -> ", head->data);
    }
    printf("NULL\n");
}

int main(void) {
    ListNode *l1 = createList("deftwxy");   
    ListNode *l2 = createList("abejlz");
    mergeSortedList(&l1, &l2);
    printList("list1", l1);
    printList("list2", l2);
}

and resulting output:

list1: a -> b -> d -> e -> e -> f -> j -> l -> t -> w -> x -> y -> z -> NULL
list2: NULL

Upvotes: 1

Related Questions