21 Merge Two Sorted Lists

1. Question

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:
1
Input:
2
1->2->4, 1->3->4
3
4
Output:
5
1->1->2->3->4->4
Copied!

2. Implementation

1
/**
2
* Definition for singly-linked list.
3
* public class ListNode {
4
* int val;
5
* ListNode next;
6
* ListNode(int x) { val = x; }
7
* }
8
*/
9
class Solution {
10
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
11
ListNode dummy = new ListNode(0);
12
ListNode p1 = l1, p2 = l2, curNode = dummy;
13
14
while (p1 != null && p2 != null) {
15
if (p1.val < p2.val) {
16
curNode.next = p1;
17
p1 = p1.next;
18
}
19
else {
20
curNode.next = p2;
21
p2 = p2.next;
22
}
23
curNode = curNode.next;
24
}
25
26
if (p1 != null) {
27
curNode.next = p1;
28
}
29
else {
30
curNode.next = p2;
31
}
32
return dummy.next;
33
}
34
}
Copied!

3. Time & Space Complexity

时间复杂度: O(n), 空间复杂度O(1)