Leetcode-21:Merge Two Sorted Lists
Merge Two Sorted Lists
Description
🔗 ​Leetcode-21. Merge Two Sorted Lists
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 non-decreasing order.
Solution
Iteration
// The question gives: an ordered array, this is very important
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode nodehead = new ListNode(-1);
ListNode pre = nodehead;
// Understand the pointing problem of pre=nodehead here
while (l1 != null && l2 != null) {
try {
if (l1.val <= l2.val) {
pre.next = l1; // I can think of both steps here
l1 = l1.next;
} else {
pre .next= l2;
l2 = l2.next;
}
// Pay attention here! The key point is the step of moving the pointer node backward.
// What about the number before pre? --- Passed to nodehead
pre = pre.next;
}catch (NullPointerException e){
}
}
// Grab the last few nodes. There may be more than one node, but they are in order, so it’s okay.
pre.next=l1==null?l2:l1;
return nodehead.next;
}
Time complexity O(n+m) Space complexity O(1) (pre and nodepre as variables)
Recursion
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1==null)
return l2;
else if(l2==null)
return l1;
//No problem till here
else if(l1.val<=l2.val) {
// Here, it is always wrong to directly return a function method body. Who exactly does it get?
// Use node.next to save elements
l1.next = mergeTwoLists(l1.next, l2);
return l1;
}
else{
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
Using node.next can achieve time complexity O(n+m) and space complexity O(m+n) (recursive function call)
Therefore, the memory consumption of the execution result is slightly slower than the saving of iterated elements.
Analysis
When I was doing it myself, I thought of these two algorithms at first, but later I always felt that something didn't work, so I gave up recursion and adopted iteration. Analyze the cause of the problem:
- How to solve the problem?
- Solve it from the beginning: --------Iteration
- Use the head element to record and the pacesetter element to move
- Solve from the tail: --------Recursion
- In order to get the saved result, use the next pointer to continue the next judgment.
- Solve it from the beginning: --------Iteration
- The key point of both is the clever use of next pointer