https://leetcode.com/problems/merge-two-sorted-lists/
This is a pretty neat problem as it expands on the sentinel pattern for solving linked list problems.
Essentially, we are given two sorted linked lists and we need to put them together such that they are ordered.
Firstly, it's important to understand we will use the pointers provided for lists to traverse them so we can expose each object making up the respective list and check it across the other list. That information will essentially tell us which object comes first.
The problem requires us to return a head and currently what we'd be doing with the two inputs makes us lose the pointer to the head. That is a clear sign that there needs to be created a sentinel node which will contain the head as it's .next.
We will also need another pointer that will serve as the extender/explorer of the sentinel node as the sentinel node solely exists to contain the head pointer. This dicussed pointer will be initially set equal to the sentinel node.
We will compare the two objects in each linked list for as long as either list isn't null, the smaller object will be set equal to the sentinel extender's .next. The list where the object came from will then move forward, and the sentinel extender will also move forward.
Finally, there we will check which of the two input lists hasn't reached their end. The sentinel extender's final .next will be equal to that list. The change will be reflected over to the sentinel node itself, whose .next property will be returned as the solution.
Space: O(1)
No additional in memory objects are created. Only pointers to existing objects are utilized.
Time: O(n + m)
We iterate over nearly every single object consisting of each linked list.
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} l1
* @param {ListNode} l2
* @return {ListNode}
*/
var mergeTwoLists = function(l1, l2) {
const sentinel = new ListNode(-1)
let prev = sentinel
while (l1 && l2) {
if (l1.val <= l2.val) {
prev.next = l1
l1 = l1.next
} else {
prev.next = l2
l2 = l2.next
}
prev = prev.next
}
prev.next = l1 ? l1 : l2
return sentinel.next
};