剑指 Offer 25. 合并两个排序的链表

题目

剑指 Offer 25. 合并两个排序的链表

题解

合并后：

最后返回dummy节点的Next节点即可。

题解

//Java
/**
 * 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) {
        //一开始设置一个虚拟节点，它的值为-1，它的值可以设置为任何的数，因为我们根本不需要使用它的值
        ListNode dummy = new ListNode(-1);

        //设置一个指针，指向虚拟节点
        ListNode pre = dummy;

        //通过一个循环，不断的比较 l1和l2 中当前的节点值的大小，直到 l1 或者 l2 遍历完毕为止
        while (l1 != null && l2 != null) {
            //如果l1当前节点的值小于等于l2当前节点的值
            if (l1.val <= l2.val) {
                //让pre指向节点的next指针指向这个更小值的节点
                //即指向l1
                pre.next = l1;
                //让l1向后移动
                l1 = l1.next;
            } else {
                //让pre指向节点的next指针指向这个更小值的节点
                //即指向l2
                pre.next = l2;
                //让l2向后移动
                l2 = l2.next;
            }
            //让pre向后移动
            pre = pre.next;
        }

        //跳出循环后，l1或者l2中可能有剩余的节点没有被观察过
        //直接把剩下的节点加入到pre的next指针位置

        //如果l1中还有节点
        if (l1 != null) {
            pre.next = l1;
        }

        if (l2 != null) {
            pre.next = l2;
        }

        return dummy.next;
    }
}

leetcode-cn执行：

执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗：41 MB, 在所有 Java 提交中击败了95.58%的用户