Merge two sorted linked lists (C)

Fork

#include <stdio.h>

int main() {
    printf("Hello world!\n");
    return 0;
}

#if 0 /* sample code */
typedef LinkedListNode* NodePtr;
NodePtr merge_sorted(NodePtr head1, NodePtr head2) {
  //TODO: Write - Your - Code
  return head1;
}
#endif

Fork

The goal of this exercise is to merge two sorted linked lists.

Problem statement: Given two sorted linked lists, merge them so the resulting linked list is also sorted.

Maintain a head and a tail pointer on the merged linked list. Choose the head of the merged linked list by comparing the first node of both linked lists.

For all subsequent nodes, choose the smaller current node and link it to the tail of the merged list. Move the current pointer of that list one step forward.

If there are still some elements in only one of the lists, link this remaining list to the tail of the merged list. Initially, the merged linked list is NULL.

Compare the value of the first two nodes and make the node with the smaller value the head node of the merged linked list. In this example, it is 4 from head1. Since it’s the first and only node in the merged list, it will be the tail. Then move head1 one step forward.

Runtime Complexity: Linear, O(m + n)
O(m+n)
, where m
m
 and n
n
 are lengths of our linked lists

Memory Complexity: Constant, O(1)
O(1)

Embed on website