Leetcode LinkedList
21. Merge Two Sorted Lists Easy
Link : https://leetcode.com/problems/mergetwosortedlists/
You are given the heads of two sorted linked lists list1
and list2
.
Merge the two lists into 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.
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]
Constraints:
 The number of nodes in both lists is in the range
[0, 50]
. 100 <= Node.val <= 100
 Both
list1
andlist2
are sorted in nondecreasing order.
Optimized solution in C++:
/**
* Definition for singlylinked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
ListNode* res = new ListNode(1);
ListNode* ans = res;
while(list1 && list2){
if(list1>val <= list2>val){
ans>next= new ListNode(list1>val);
list1= list1>next;
}
else{
ans>next= new ListNode(list2>val);
list2= list2>next;
}
ans= ans>next;
}
if(list1){
ans>next= list1;
}
if(list2){
ans>next= list2;
}
return res>next;
}
};
Solution Explanation:
Merging Two Sorted Lists
This solution is about combining two sorted lists (let's call them list1
and list2
) into one single sorted list. Imagine you have two lines of people, each line is ordered by height. You want to form a new line that keeps everyone in order of height, pulling the shortest person available from the front of either line each time.
How It Works

Creating a Starting Point: First, we create an imaginary person (or a temporary starting node) that stands before the new line starts forming. This helps us easily add people to the new line without worrying about who is first.

Comparing Heights (Values): We look at the first person in each line. Whichever person is shorter (or if they're the same height, it doesn't matter which one we choose), we add them to the end of the new line and then step forward in the line they came from.

Repeating the Process: We keep doing this  comparing the first person in each line, adding the shorter one to the new line, and stepping forward in their line. If one line runs out of people, we simply add the rest of the people from the other line to the end of the new line.

Final Step: After we've gone through both lines entirely, our new line is complete. But remember the imaginary person we placed at the start? They're not actually part of the new line, so we make sure the new line starts with the first real person we added.
Technical Explanation
 A new list node (
res
) with a value of1
is created to act as the starting point. Theans
pointer is used to add new nodes to the list.  As long as there are elements in both
list1
andlist2
, we compare their values. If
list1
's value is less than or equal tolist2
's, we addlist1
's value to the new list and movelist1
forward.  Otherwise, we add
list2
's value and movelist2
forward.
 If
 If we reach the end of one list, we connect the remaining elements of the other list directly to the new list.
 Finally, since the first node (
1
) was just a placeholder, we return the list starting from the next node, which is the actual start of our merged list.
This solution effectively merges two sorted lists into one, maintaining the sorted order, with a time complexity that is linear to the combined length of the two lists.