#include <cassert>
#include <iostream>
#include <limits>
#include <memory>
#include <random>
#include <string>
#include <memory>
template <typename T> struct ListNode {
T data;
std::shared_ptr<ListNode<T> > prev, next;
};
template <typename T>
void append_node(std::shared_ptr<ListNode<T> > *node,
std::shared_ptr<ListNode<T> > *tail) {
(*node)->prev = *tail;
(*tail)->next = *node;
*tail = *node; // resets tail to the last node.
*node = (*node)->next;
}
template <typename T>
decltype(auto) merge_sorted_linked_lists(std::shared_ptr<ListNode<T> > F,
std::shared_ptr<ListNode<T> > L) {
// create a placeholder for the result
auto dummy_head = std::make_shared<ListNode<T> >();
auto tail = dummy_head;
while (F && L) {
append_node(F->data < L->data ? &F : &L, &tail);
}
// append remaining nodes of F or L
tail->next = F ? F : L;
return dummy_head->next;
}
int main(int argc, char *argv[]) {
std::default_random_engine gen((std::random_device())());
for (int times = 0; times < 10000; ++times) {
std::shared_ptr<ListNode<int> > F = nullptr, L = nullptr;
int n, m;
if (argc == 3) {
n = std::stoi(argv[1]), m = std::stoi(argv[2]);
} else if (argc == 2) {
n = std::stoi(argv[1]), m = std::stoi(argv[1]);
} else {
std::uniform_int_distribution<int> dis(0, 99);
n = dis(gen), m = dis(gen);
}
for (int i = n; i > 0; --i) {
auto temp = std::make_shared<ListNode<int> >(
ListNode<int>{ i, nullptr, nullptr });
temp->next = F;
if (F)
F->prev = temp;
F = temp;
}
for (int j = m; j > 0; --j) {
auto temp = std::make_shared<ListNode<int> >(
ListNode<int>{ j, nullptr, nullptr });
temp->next = L;
if (L)
L->prev = temp;
L = temp;
}
auto sorted_head = merge_sorted_linked_lists(F, L);
std::shared_ptr<ListNode<int> > sorted_tail = nullptr;
int count = 0;
int pre = std::numeric_limits<int>::min();
while (sorted_head) {
assert(pre <= sorted_head->data);
pre = sorted_head->data;
sorted_tail = sorted_head;
sorted_head = sorted_head->next;
++count;
}
// Make sure the merged list have the same number of nodes as F and L.
assert(count == n + m);
int count_backward = 0;
int post = std::numeric_limits<int>::max();
while (sorted_tail) {
assert(post >= sorted_tail->data);
post = sorted_tail->data;
sorted_tail = sorted_tail->prev;
++count_backward;
}
// Make sure the merged list have the same number of nodes as F and L
// backwards.
std::cout << count << "==" << count_backward << std::endl;
assert(count_backward == n + m);
}
return 0;
}
Sample Run:
prem@prem-Vostro-2420:~/Prog_Intv_CookBook/LinkedList/code/LinkedList$ g++ -g -std=c++14 MergeSortedDoublyLinkedList.cpp
prem@prem-Vostro-2420:~/Prog_Intv_CookBook/LinkedList/code/LinkedList$ ./a.out 145==145
134==134
70==70
158==158
112==112
81==81
159==159
67==67
110==110
53==53
135==135
176==176
105==105
95==95
66==66
94==94
78==78
119==119
68==68
117==117
158==158
109==109
95==95
57==57
111==111
91==91
48==48
93==93
105==105
93==93
83==83
168==168
147==147
119==119
104==104
115==115
13==12
a.out: MergeSortedDoublyLinkedList.cpp:98: int main(int, char**): Assertion `count_backward == n + m' failed.
Aborted (core dumped)
prem@prem-Vostro-2420:~/Prog_Intv_CookBook/LinkedList/code/LinkedList$
What’s wrong with this code? Can you please help identify?