title: Merge Two Sorted Lists
tags:
- merge-two-sorted-lists
- No.21
- simple
- merge
- loop-optimization
- list
Problem
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
Corner Cases
- empty list
Input: []
[]
return: []
Solutions
Merge Sort
Just the same as the merge part of merge sort. To avoid too much if-else in loop:
- Take
ListNode[]array and index to denote the target. - Initialize outside the loop.
The list update:
0.0. initialization with l1
[l1, p1, hd] -> x -> x
[l2, p2] -> x -> x -> x
0.1.
[l1, p1, hd] -> [np] -> x
[l2, p2] -> x -> x -> x
0.2.
[p1, np] -> x -> x -> x
[l2, p2] -> x -> x -> x
[hd, px]
1. before updating
[p1] -> x -> x -> x
[p2] -> x -> x -> x
[px]
2. choose p1
[p1] -> [np] -> x -> x
[p2] -> x -> x -> x
[px]
3.
[px] -> [p1] -> [np] -> x -> x
[p2] -> x -> x -> x
4.
x -> [p1, px] -> [np] -> x -> x
[p2] -> x -> x -> x
5.
[np] -> x -> x -> x
[p2] -> x -> x -> x
x -> [px]
6.
[p1, np] -> x -> x -> x
[p2] -> x -> x -> x
x -> [px]
Running time is O(min(l_1, l_2)), since we directly copy the rest of l2 to target list hd when l1 comes to null first.
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) { return l2; }
else if (l2 == null) { return l1; }
ListNode[] ps = new ListNode[] {l1, l2};
int id = (ps[0].val <= ps[1].val) ? 0 : 1;
ListNode hd = ps[id];
ListNode px = hd;
ListNode np = ps[id].next;
ps[id] = np;
while (ps[0] != null && ps[1] != null) {
id = (ps[0].val <= ps[1].val) ? 0 : 1;
np = ps[id].next;
px.next = ps[id];
px = px.next;
px.next = null;
ps[id] = np;
}
// copy the residual list
px.next = (ps[1] == null) ? ps[0] : ps[1];
return hd;
}
}
