合并两个有序链表

发表于 | 分类于

题目：（LeetCode.21）合并两个有序链表

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

示例：

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

解法

这个一个简单的链表操作问题。在两个输入链表均不为空的时候，将较小的一个元素插入新链表中，并将那个较小链表的表首先后移一位。

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        int rootVal;
        if (l1.val < l2.val) {
            rootVal = l1.val;
            l1 = l1.next;
        } else {
            rootVal = l2.val;
            l2 = l2.next;
        }
        ListNode root = new ListNode(rootVal);
        ListNode temp = root;
        for (; ; ) {
            if (l1 != null && l2 != null) {
                if (l1.val < l2.val) {
                    temp.next = new ListNode(l1.val);
                    l1 = l1.next;
                } else {
                    temp.next = new ListNode(l2.val);
                    l2 = l2.next;
                }
                temp = temp.next;
            }else {
                if (l1 == null) {
                    temp.next = l2;
                }
                if (l2 == null) {
                    temp.next = l1;
                }
                break;
            }
        }
        return root;
    }

    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }
}