The Royal Coding
Binary Search
Bubble Sort
Build A Max Heap
Build A Min Heap
Graph Traversal
Heap Sort
Implementing A Basic Hash Table
Implementing A Binary Search Tree
Implementing A Queue
Implementing A Stack
Insertion Sort
Length Of Linked List
Linear Search
Linked Lists
Merge A Two Sorted Linked List
Merge Sort
Quick Sort
Redix Sort
Reverse A Linked List
Selection Sort
Ternary Search
Suffix Automata Construction
Python/C/C++/JAVA
Advanced Practice Programs with Code and Concept
By D.S
Merge a two sorted linked list int a Single linked list
If you need to merge two sorted linked lists into a single sorted list, there are a few programming languages that can get the job done effectively. Among these include C, C++, Python, and Java. In any of these languages, you'll first want to create a new empty linked list that will eventually contain all of the nodes from both original lists. Then, iterate through each list in order and compare the values of their respective nodes. Whichever node has the lower value should be added to your new list first, with the process repeating until both original lists have been exhausted. Finally, once all of the values have been added to your new linked list in order, return this merged list as your final result! With a little programmatic know-how in any of these popular coding languages, merging two sorted linked lists is easier than you might think!
(a.) C Code
#include <stdio.h>
#include <stdlib.h> // Needed for malloc
struct Node {
int data;
struct Node* next;
};
struct Node* mergeLists(struct Node* list1, struct Node* list2) {
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (list1->data < list2->data) {
list1->next = mergeLists(list1->next, list2);
return list1;
} else {
list2->next = mergeLists(list1, list2->next);
return list2;
}
}
void printList(struct Node* head) {
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n"); // Add newline for better formatting
}
// Helper function to create a new node
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->next = NULL;
return node;
}
// Helper function to append a node to the list
void append(struct Node** head, int data) {
struct Node* new_node = newNode(data);
if (*head == NULL) {
*head = new_node;
return;
}
struct Node* last = *head;
while (last->next != NULL) {
last = last->next;
}
last->next = new_node;
}
int main() {
struct Node* list1 = NULL;
struct Node* list2 = NULL;
// Create sample sorted lists
append(&list1, 1);
append(&list1, 3);
append(&list1, 5);
append(&list2, 2);
append(&list2, 4);
append(&list2, 6);
printf("List 1: ");
printList(list1);
printf("List 2: ");
printList(list2);
struct Node* mergedList = mergeLists(list1, list2);
printf("Merged List: ");
printList(mergedList);
// Note: In a real program, you should free the allocated memory
return 0;
}Output:-
1 2 3 4 5 6
(b.) C++ Code
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
};
Node* mergeLists(Node* list1, Node* list2) {
if (list1 == NULL)
return list2;
if (list2 == NULL)
return list1;
if (list1->data < list2->data) {
list1->next = mergeLists(list1->next, list2);
return list1;
} else {
list2->next = mergeLists(list1, list2->next);
return list2;
}
}
void printList(Node* head) {
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
int main() {
// Example initialization of list1: 1->3->5
Node* list1 = new Node{1, new Node{3, new Node{5, NULL}}};
// Example initialization of list2: 2->4->6
Node* list2 = new Node{2, new Node{4, new Node{6, NULL}}};
Node* mergedList = mergeLists(list1, list2);
cout << "Merged List: ";
printList(mergedList);
return 0;
}Output:-
1 2 3 4 5 6
(c.) Python Code
class Node:
def __init__(self, data):
self.data = data
self.next = None
def merge_lists(list1, list2):
if not list1:
return list2
if not list2:
return list1
if list1.data < list2.data:
list1.next = merge_lists(list1.next, list2)
return list1
else:
list2.next = merge_lists(list1, list2.next)
return list2
def print_list(head):
while head:
print(head.data, end=" ")
head = head.next
# Example usage:
# Create two sorted linked lists
list1 = Node(1)
list1.next = Node(3)
list1.next.next = Node(5)
list2 = Node(2)
list2.next = Node(4)
list2.next.next = Node(6)
# Merge the lists
merged_list = merge_lists(list1, list2) # Fixed typo: merge_lists instead of merge_lists
print("Merged List:", end=" ")
print_list(merged_list)Output:-
1 2 3 4 5 6
(d.) Java Code
import java.util.*;
class ListNode {
int data;
ListNode next;
ListNode(int data) {
this.data = data;
this.next = null;
}
}
public class MergeSortedLinkedLists {
public static ListNode mergeLists(ListNode list1, ListNode list2) {
if (list1 == null)
return list2;
if (list2 == null)
return list1;
if (list1.data < list2.data) {
list1.next = mergeLists(list1.next, list2);
return list1;
} else {
list2.next = mergeLists(list1, list2.next);
return list2;
}
}
public static void printList(ListNode head) {
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
}
public static void main(String[] args) {
ListNode list1 = new ListNode(1);
list1.next = new ListNode(3);
list1.next.next = new ListNode(5);
ListNode list2 = new ListNode(2);
list2.next = new ListNode(4);
list2.next.next = new ListNode(6);
// Assuming list1 and list2 are initialized with sorted values
ListNode mergedList = mergeLists(list1, list2);
System.out.print("Merged List: ");
printList(mergedList);
}
}Output:-
1 2 3 4 5 6
How did you feel about this post?
😍
🙂
😐
😕
😡
Was this helpful?
👍
👎