Merge two sorted linked lists (HackerRank)
Problem
Given pointers to the heads of two sorted linked lists, merge them into a single, sorted linked list. Either head pointer may be null meaning that the corresponding list is empty.
Example
- $headA$ refers to $1 \rightarrow 3 \rightarrow 7 \rightarrow \text{NULL}$
- $headB$ refers to $1 \rightarrow 2 \rightarrow \text{NULL}$
- The new list is $1 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 7 \rightarrow \text{NULL}$
Function Description
mergeLists function has the following parameters:
SinglyLinkedListNodepointerheadA: a reference to the head of the first list;SinglyLinkedListNodepointerheadB: a reference to the head of the second list.
Returns
SinglyLinkedListNodepointer: a reference to the head of the merged list.
Input Format
The first line contains an integer $t$, the number of test cases.
The format for each test case is as follows:
- The first line contains an integer $n$, the length of the first linked list.
- The next $n$ lines contain an integer each, the elements of the first linked list.
- The next line contains an integer $m$, the length of the second linked list.
- The next $m$ lines contain an integer each, the elements of the second linked list.
Constraints
- $1 \leq t \leq 10$
- $1 \leq n,~m \leq 1000$
- $1 \leq list[i] \leq 1000$, where $list[i]$ is the $i^{th}$ element of the list
Sample Test Case
Input
1
3
1
2
3
2
3
4Output
1 2 3 3 4Explanation
- The first linked list is: $1 \rightarrow 2 \rightarrow 3 \rightarrow \text{NULL}$
- The second linked list is: $3 \rightarrow 4 \rightarrow \text{NULL}$
- Hence, the merged linked list is: $1 \rightarrow 2 \rightarrow 3 \rightarrow 3 \rightarrow 4 \rightarrow \text{NULL}$
Solution
1#include <bits/stdc++.h>
2
3using namespace std;
4
5class SinglyLinkedListNode {
6 public:
7 int data;
8 SinglyLinkedListNode *next;
9
10 SinglyLinkedListNode(int node_data) {
11 this->data = node_data;
12 this->next = nullptr;
13 }
14};
15
16class SinglyLinkedList {
17 public:
18 SinglyLinkedListNode *head;
19 SinglyLinkedListNode *tail;
20
21 SinglyLinkedList() {
22 this->head = nullptr;
23 this->tail = nullptr;
24 }
25
26 void insert_node(int node_data) {
27 SinglyLinkedListNode* node = new SinglyLinkedListNode(node_data);
28
29 if (!this->head) {
30 this->head = node;
31 } else {
32 this->tail->next = node;
33 }
34
35 this->tail = node;
36 }
37};
38
39void print_singly_linked_list(SinglyLinkedListNode* node, string sep, ofstream& fout) {
40 while (node) {
41 fout << node->data;
42
43 node = node->next;
44
45 if (node) {
46 fout << sep;
47 }
48 }
49}
50
51void free_singly_linked_list(SinglyLinkedListNode* node) {
52 while (node) {
53 SinglyLinkedListNode* temp = node;
54 node = node->next;
55
56 free(temp);
57 }
58}
59
60SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {
61 if (!head1) return head2;
62 if (!head2) return head1;
63
64 auto i = head1, j = head2;
65 if (i->data > j->data) swap(i, j);
66 auto merged = i;
67
68 while (i->next && j) {
69 if (i->next->data > j->data) {
70 swap(i->next, j->next);
71 swap(i->next, j);
72 } else i = i->next;
73 }
74 if (j) i->next = j;
75
76 return merged;
77}
78
79int main() {
80 ofstream fout(getenv("OUTPUT_PATH"));
81
82 int tests;
83 cin >> tests;
84 cin.ignore(numeric_limits<streamsize>::max(), '\n');
85
86 for (int tests_itr = 0; tests_itr < tests; tests_itr++) {
87 SinglyLinkedList* llist1 = new SinglyLinkedList();
88
89 int llist1_count;
90 cin >> llist1_count;
91 cin.ignore(numeric_limits<streamsize>::max(), '\n');
92
93 for (int i = 0; i < llist1_count; i++) {
94 int llist1_item;
95 cin >> llist1_item;
96 cin.ignore(numeric_limits<streamsize>::max(), '\n');
97
98 llist1->insert_node(llist1_item);
99 }
100
101 SinglyLinkedList* llist2 = new SinglyLinkedList();
102
103 int llist2_count;
104 cin >> llist2_count;
105 cin.ignore(numeric_limits<streamsize>::max(), '\n');
106
107 for (int i = 0; i < llist2_count; i++) {
108 int llist2_item;
109 cin >> llist2_item;
110 cin.ignore(numeric_limits<streamsize>::max(), '\n');
111
112 llist2->insert_node(llist2_item);
113 }
114
115 SinglyLinkedListNode* llist3 = mergeLists(llist1->head, llist2->head);
116
117 print_singly_linked_list(llist3, " ", fout);
118 fout << "\n";
119
120 free_singly_linked_list(llist3);
121 }
122
123 fout.close();
124
125 return 0;
126}Merge Two Sorted Lists (LeetCode)
Problem
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Constraints
- The number of nodes in both lists is in the range
[0, 50]. -100 <= Node.val <= 100.- Both
list1andlist2are sorted in non-decreasing order.
Example 1
Input
list1 = [1,2,4], list2 = [1,3,4]Output
[1,1,2,3,4,4]Example 2
Input
list1 = [], list2 = []Output
[]Example 3
Input
list1 = [], list2 = [0]Output
[0]Solution
1class Solution {
2public:
3 ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
4 // Trivial cases with at least one empty list
5 if (!list1) return list2;
6 if (!list2) return list1;
7
8 auto i = list1, j = list2;
9 if (i->val > j->val) swap(i, j);
10 // `i` points to the list with a lesser first element (at index 0)
11 auto merged = i; // Head of the merged list
12
13 // Traverse lists until the shorter list ends
14 while (i->next && j) {
15 if (i->next->val > j->val) {
16 swap(i->next, j->next);
17 swap(i->next, j);
18 } else i = i->next;
19 }
20 // Append elements from the longer list (if any)
21 if (j) i->next = j;
22
23 return merged;
24 }
25};