Hello,
I’m trying to solve this problem in Zig, but not fully sure about the syntax.
I’ve tried the below implementation with a unit test:
const std = @import("std");
const testing = std.testing;
const ListNode = struct {
value: i16,
next: ?*ListNode = null,
};
fn mergeTwoSortedLists(list1: ?*ListNode, list2: ?*ListNode) ?*ListNode {
const first: ListNode = undefined;
var merged_list = first;
var l1, var l2 = .{ list1, list2 };
while (l1 != null and l2 != null) {
if (l1.?.value < l2.?.value) {
merged_list.next = l1;
l1 = l1.?.next;
} else {
merged_list.next = l2;
l2 = l2.?.next;
}
merged_list = merged_list.?.next;
}
if (l1 != null) {
merged_list.next = l1;
} else {
merged_list.next = l2;
}
return first.?.next;
}
test "example 1 - lists are of different lengths and contain duplicates" {
var l1_node3 = ListNode{ .value = 5, .next = null };
var l1_node2 = ListNode{ .value = 2, .next = &l1_node3 };
var l1_node1 = ListNode{ .value = 1, .next = &l1_node2 };
var l2_node3 = ListNode{ .value = 5, .next = null };
var l2_node2 = ListNode{ .value = 5, .next = &l2_node3 };
var l2_node1 = ListNode{ .value = 5, .next = &l2_node2 };
var tc_node6 = ListNode{ .value = 5, .next = null };
var tc_node5 = ListNode{ .value = 4, .next = &tc_node6 };
var tc_node4 = ListNode{ .value = 3, .next = &tc_node5 };
var tc_node3 = ListNode{ .value = 2, .next = &tc_node4 };
var tc_node2 = ListNode{ .value = 1, .next = &tc_node3 };
var tc_node1 = ListNode{ .value = 1, .next = &tc_node2 };
const result = mergeTwoSortedLists(&l1_node1, &l2_node1);
try testing.expectEqualDeep(&tc_node1, result);
}
which fails with:
error: expected optional type, found 'merge_two_sorted_lists.ListNode'
merged_list = merged_list.?.next;
Additionally, tried a few other things but they give diffferent errors.
Appreciate any feedback!
Hello,
Its quite smple, you never specified type of merged_list.
It is infered in var merged_list = first; but this inference makes it the exact type of first, which is non-nullable ListNode.
The fix it, specify merged_list as nullable pointer type:
var merged_list: ?*ListNode = &first;
OR you can just remove the .? in merged_list = merged_list .?.next;
This will need some more changes over the code tho.
BUT this is not the only solution to your problem. You can for example construct the returned ListNode without copying it to the stack, just by using its pointer.
The fix it, specify merged_list as nullable pointer type:
var merged_list: ?*ListNode = &first;
This doesn’t seem to work
It fixes the current problem.
You have more of them, give me a sec and i will try to fix the code.
Also i strongly reccomend to look at some tutorial to the language (ziglings/exercises: Learn the ⚡Zig programming language by fixing tiny broken programs. - Codeberg.org). This seems like you are a bit confused on nullable types and pointers. I mean it in the best way, ziglings are awsome, i really liked them.
3 Likes
Ok i finalized relatively simple solution:
const std = @import("std");
const testing = std.testing;
const ListNode = struct {
value: i16,
next: ?*ListNode = null,
};
fn mergeTwoSortedLists(list1: ?*ListNode, list2: ?*ListNode) ?*ListNode {
var tmp: ListNode = undefined;
var tail = &tmp;
var l1 = list1;
var l2 = list2;
while (l1 != null and l2 != null) {
if (l1.?.value < l2.?.value) {
tail.next = l1;
l1 = l1.?.next;
} else {
tail.next = l2;
l2 = l2.?.next;
}
tail = tail.next.?;
}
tail.next = if (l1 == null) l2 else l1;
return tmp.next;
}
test "example 1 - lists are of different lengths and contain duplicates" {
var l1_node3 = ListNode{ .value = 5, .next = null };
var l1_node2 = ListNode{ .value = 2, .next = &l1_node3 };
var l1_node1 = ListNode{ .value = 1, .next = &l1_node2 };
var l2_node4 = ListNode{ .value = 8, .next = null };
var l2_node3 = ListNode{ .value = 5, .next = &l2_node4 };
var l2_node2 = ListNode{ .value = 5, .next = &l2_node3 };
var l2_node1 = ListNode{ .value = 4, .next = &l2_node2 };
const result = mergeTwoSortedLists(&l1_node1, &l2_node1);
var current = result;
var prev: ?*ListNode = null;
while (current) |existing_current| {
std.debug.print("Found: \"{}\"\n", .{existing_current.value});
if (prev) |p| {
try testing.expect(p.value <= existing_current.value);
}
prev = existing_current;
current = existing_current.next;
}
}
There are many ways you can do this, this is just a solution really close to your code.
Main issues:
- Confusing pointers and actual values they point to.
- Because of 1. doing changes only on function local copies instead of the original nodes.
- In your testing nor deep nor shallow equality will work. Deep equal check will fail because the pointers of “tc_” versions point to different places on the stack then the “l1_” and “l2_” versions and shallow one wont follow the whole list. Simplest way to fix it, is just itterate thru it and check if it is sorted!
Hope i was able to help a bit, otherwise you were really close 
4 Likes
Thanks, this was immensely helpful !
1 Like
Looks like testing.expectEqualDeep works with your solution:
test mergeTwoSortedLists {
{ // lists are of different lengths and contain duplicates
var l1_node3 = ListNode{ .value = 5, .next = null };
var l1_node2 = ListNode{ .value = 2, .next = &l1_node3 };
var l1_node1 = ListNode{ .value = 1, .next = &l1_node2 };
var l2_node3 = ListNode{ .value = 4, .next = null };
var l2_node2 = ListNode{ .value = 3, .next = &l2_node3 };
var l2_node1 = ListNode{ .value = 1, .next = &l2_node2 };
var tc_node6 = ListNode{ .value = 5, .next = null };
var tc_node5 = ListNode{ .value = 4, .next = &tc_node6 };
var tc_node4 = ListNode{ .value = 3, .next = &tc_node5 };
var tc_node3 = ListNode{ .value = 2, .next = &tc_node4 };
var tc_node2 = ListNode{ .value = 1, .next = &tc_node3 };
var tc_node1 = ListNode{ .value = 1, .next = &tc_node2 };
const result = mergeTwoSortedLists(&l1_node1, &l2_node1);
try testing.expectEqualDeep(&tc_node1, result);
}
{ // merging empty lists
const result = mergeTwoSortedLists(null, null);
try testing.expect(result == null);
}
{ // merging an empty list with a non-empty list
var l2_node2 = ListNode{ .value = 8, .next = null };
var l2_node1 = ListNode{ .value = 5, .next = &l2_node2 };
var tc_node2 = ListNode{ .value = 8, .next = null };
var tc_node1 = ListNode{ .value = 5, .next = &tc_node2 };
const result = mergeTwoSortedLists(null, &l2_node1);
try testing.expectEqualDeep(&tc_node1, result);
}
{
// merging a non-empty list with an empty list
var l1_node2 = ListNode{ .value = 9, .next = null };
var l1_node1 = ListNode{ .value = 7, .next = &l1_node2 };
var tc_node2 = ListNode{ .value = 9, .next = null };
var tc_node1 = ListNode{ .value = 7, .next = &tc_node2 };
const result = mergeTwoSortedLists(&l1_node1, null);
try testing.expectEqualDeep(&tc_node1, result);
}
{ // both lists contain the same values
var l1_node3 = ListNode{ .value = 32, .next = null };
var l1_node2 = ListNode{ .value = 21, .next = &l1_node3 };
var l1_node1 = ListNode{ .value = 10, .next = &l1_node2 };
var l2_node3 = ListNode{ .value = 32, .next = null };
var l2_node2 = ListNode{ .value = 21, .next = &l2_node3 };
var l2_node1 = ListNode{ .value = 10, .next = &l2_node2 };
var tc_node6 = ListNode{ .value = 32, .next = null };
var tc_node5 = ListNode{ .value = 32, .next = &tc_node6 };
var tc_node4 = ListNode{ .value = 21, .next = &tc_node5 };
var tc_node3 = ListNode{ .value = 21, .next = &tc_node4 };
var tc_node2 = ListNode{ .value = 10, .next = &tc_node3 };
var tc_node1 = ListNode{ .value = 10, .next = &tc_node2 };
const result = mergeTwoSortedLists(&l1_node1, &l2_node1);
try testing.expectEqualDeep(&tc_node1, result);
}
}
I just read the documentation around it, you are right.
It ignores pointers itself, cares only about the values they point to.
Thanks for correction👍