21. 合并两个有序链表

Posted on | In
Words count in article: 229 | Reading time ≈ 1

题目

将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

两个升序链表

示例1：

1
2
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

解法

解法一：遍历合并

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {	
		if (null == l1) {
			return l2;
		}
		
		if (null == l2) {
			return l1;
		}
		
		ListNode dummyNode = new ListNode(-1);
		ListNode dummy = dummyNode;
		while (null != l1 && null != l2) {
			if (l1.val <= l2.val) {
				dummy.next = l1;
				l1 = l1.next;
			} else {
				dummy.next = l2;
				l2 = l2.next;
			}
			dummy = dummy.next;
		}
		
		dummy.next = l1 == null ? l2 : l1;
		return dummyNode.next;
	}

解法二：递归

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (null == l1) {
			return l2;
		}
		
		if (null == l2) {
			return l1;
		}
		
		if (l1.val < l2.val) {
			l1.next = mergeTwoLists(l1.next, l2);
			return l1;
		} else {
			l2.next = mergeTwoLists(l1, l2.next);
			return l2;
		}
    }

参考资料

LeetCode-合并两个有序链表-题解

0%