700176. Merge two sorted linked lists
Medium
Merge two sorted linked lists
Slug: merge-two-sorted-linked-lists
Difficulty: Medium
Id: 700176
Topic Tags: Linked List, Data Structures
Company Tags: Zoho, Flipkart, Accolite, Amazon, Microsoft, Samsung, FactSet, MakeMyTrip, Oracle, Brocade, Synopsys, OATS Systems, Belzabar
Summary
Merge two sorted linked lists into one sorted linked list. The function should merge the two linked lists in a way that the merged list is also sorted.
Detailed Explanation
To solve this problem, we will iterate through both linked lists and compare their node values. We will add the smaller value to our result list and move to the next node until one of the lists becomes empty. Then, we will append the remaining nodes from the other list to the result list.
Here is a step-by-step breakdown of the solution:
- Initialize two pointers,
pandq, to the beginning of both linked lists. - Compare the values at
pandq. The smaller value should be added to the result list. - Move the pointer pointing to the node with the smaller value to its next node.
- Repeat steps 2-3 until one of the lists becomes empty.
- If one list is not empty, append all the nodes from that list to the result list.
The time complexity for this solution is O(n + m), where n and m are the lengths of the two input linked lists. The space complexity is O(n + m) as well, as we need to store the merged linked list in memory.
Optimized Solutions
Java
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
ListNode result = new ListNode(0);
ListNode current = result;
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
current.next = l1;
l1 = l1.next;
} else {
current.next = l2;
l2 = l2.next;
}
current = current.next;
}
current.next = l1 != null ? l1 : l2;
return result.next;
}