This content originally appeared on DEV Community and was authored by Johns Code
Today, we look at another linked list task.
Create a function to merge 2 sorted linked lists. The resulting list should be a sorted list using the nodes of the 2 lists.
For this, we will use the generic linked list implementation from the previous post which can be found here
func mergeSortedLists(ll1 LinkedList[int], ll2 LinkedList[int]) LinkedList[int] {
result := LinkedList[int]{}
p1 := ll1.Head
p2 := ll2.Head
rp := &Node[int]{} // dummy node as result head
result.Head = rp
for p1 != nil && p2 != nil {
if p1.Data >= p2.Data {
rp.Next = p2
p2 = p2.Next
} else {
rp.Next = p1
p1 = p1.Next
}
rp = rp.Next
}
if p1 != nil {
rp.Next = p1
}
if p2 != nil {
rp.Next = p2
}
result.Head = result.Head.Next
return result
}
The logic is pretty easy to follow. First, we setup pointers to the heads of the 2 lists and the resulting list. Since we don't know the 'head' of the resulting list, we create a dummy node as a placeholder (we'll fix that one later). We also create a current node, rp, for the result list.
Next, we iterate over the 2 lists. We have a current node for each list. At each step, we look at which of the 2 current nodes has the smaller value and put that node on the result list. Then move the current node of that list (the one that was smaller) to the next node in the list. We also need to move the current node of the result to the next place.
Our loop logic is simply to keep doing this until we reach the end of one of the lists. At this point, we know that there are no more elements to compare for one of the lists; they are already in the result list. So, we can then simply put the remaining nodes of the other list at the end of the result, since we know they are already sorted.
How would you do this different? Can we optimize this? Let me know in the comments.
Thanks!
The code for this post and all posts in this series can be found here
This content originally appeared on DEV Community and was authored by Johns Code
Johns Code | Sciencx (2024-07-13T01:18:44+00:00) Merge 2 sorted lists. Retrieved from https://www.scien.cx/2024/07/13/merge-2-sorted-lists/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.