【LeetCode】合并两个有序链表 Java 题解

作者：Albert

2022-10-14
北京
本文字数：1121 字
阅读完需：约 4 分钟

题目描述

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

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []输出：[]
示例 3：
输入：l1 = [], l2 = [0]输出：[0] 
来源：力扣（LeetCode）链接：https://leetcode.cn/problems/merge-two-sorted-lists/description/著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

复制代码

思路分析

今天的算法题目是链表题目。将两个升序链表合并为一个新的升序链表并返回。首先，简单介绍一下链表。链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。
具体到这个题目，我们采用类似归并排序的算法，基于分治思想将分段排序后链表合并。由于链表已分段排序，各链表的首元素的最小值即是当前链表的最小值，不断从链表中取出当前最小值至辅助链表即可使其有序。
在解题过程中，使用了 dummy 节点，也叫保护节点。它的作用是什么呢？在对单链表进行操作时，dummy 的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。
具体实现代码如下，供参考。

通过代码

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode() {} *     ListNode(int val) { this.val = val; } *     ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        ListNode dummy = new ListNode(-1);        ListNode cur = dummy;        while(list1!=null && list2!=null) {            if(list1.val < list2.val) {                cur.next = new ListNode(list1.val);                list1 = list1.next;            }else {                cur.next = new ListNode(list2.val);                list2 = list2.next;            }            cur = cur.next;        }        while(list1!=null) {            cur.next = new ListNode(list1.val);            list1 = list1.next;            cur = cur.next;        }        while(list2!=null) {            cur.next = new ListNode(list2.val);            list2 = list2.next;            cur = cur.next;        }        return dummy.next;
    }}