21. 合并两个有序链表

题目描述

原题
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例1:
1
输入:l1 = [1,2,4], l2 = [1,3,4]
2
输出:[1,1,2,3,4,4]
Copied!
示例 2:
1
输入:l1 = [], l2 = []
2
输出:[]
Copied!
示例 3:
1
输入:l1 = [], l2 = [0]
2
输出:[0]
Copied!

题解

递归

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
if(l1 == null) return l2;
12
if(l2 == null) return l1;
13
if(l1.val < l2.val){
14
l1.next = mergeTwoLists(l1.next,l2);
15
return l1;
16
}else{
17
l2.next = mergeTwoLists(l1,l2.next);
18
return l2;
19
}
20
}
21
}
Copied!

迭代

1
class Solution {
2
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
3
ListNode dummyNode = new ListNode(-1);
4
ListNode cur = dummyNode;
5
//两个都不为null
6
while(l1!=null&&l2!=null){
7
if(l1.val < l2.val){
8
cur.next = l1;
9
l1 = l1.next;
10
}else{
11
cur.next = l2;
12
l2 = l2.next;
13
}
14
cur = cur.next;
15
}
16
//走到这里说明有一个为null
17
cur.next = l1!=null?l1:l2;
18
return dummyNode.next;
19
}
20
}
Copied!
最近更新 4mo ago