Merging two sorted linked lists

by

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;
}

More Related Contents:

  1. How to reverse a singly linked list using only two pointers?
  2. Recursive and non-recursive traversal of three degree tree
  3. C – How to implement Set data structure?
  4. Deleting a middle node from a single linked list when pointer to the previous node is not available
  5. Linked list recursive reverse
  6. Finding the intersecting node from two intersecting linked lists
  7. Sorting a linked list
  8. Does C have any tools for doing string addition?
  9. Sorting (Quicksort) ,Partition
  10. Fast way to tokenize a string in c
  11. What is the fastest substring search algorithm?
  12. How to detect a loop in a linked list?
  13. What is the reason for using a double pointer when adding a node in a linked list?
  14. Point in Polygon Algorithm
  15. What common algorithms are used for C’s rand()?
  16. Matrix multiplication: Small difference in matrix size, large difference in timings
  17. Relative performance of std::vector vs. std::list vs. std::slist?
  18. Enumerate factors of a number directly in ascending order without sorting?
  19. How to find the element of an array that is repeated at least N/2 times?
  20. read line by line in the most efficient way *platform specific*
  21. Finding all the unique permutations of a string without generating duplicates
  22. Print all permutation in lexicographic order
  23. Perceptron learning algorithm not converging to 0
  24. Given an audio stream, find when a door slams (sound pressure level calculation?)
  25. find if 4 points on a plane form a rectangle?
  26. signed and unsigned arithmetic implementation on x86
  27. Reductions in parallel in logarithmic time
  28. Extend a line segment a specific distance
  29. Automated field re-ordering in C structs to avoid padding
  30. How to apply binary search O(log n) on a sorted linked list?

Leave a Comment