【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表-Toy模板网

这篇具有很好参考价值的文章主要介绍了【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表,算法数据结构,算法,笔记,链表

简单

相关标签

相关企业

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

示例 1：
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
示例 2：
输入：l1 = [], l2 = []
输出：[]
示例 3：
输入：l1 = [], l2 = [0]
输出：[0]
提示：文章来源地址https://www.toymoban.com/news/detail-838708.html

两个链表的节点数目范围是 [0, 50]

-100 <= Node.val <= 100

l1 和 l2 均按 非递减顺序 排列

思路

拉拉链法
- 两个链表就相当于拉链两侧的锯齿，虚拟头节点的指针就相当于拉链的拉锁，将两个有序链表合并。
虚拟头节点
- 虚拟出来的，本身不存储值。
双指针
- 链表题常见，规避头节点为空指针的情况。

解答

/**
 * 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(), p1 = list1, p2 = list2;
        ListNode p = dummy;

        while (p1 != null && p2 != null) {
            if (p1.val < p2.val) {
                p.next = p1;
                p1 = p1.next;
            } else {
                p.next = p2;
                p2 = p2.next;
            }

            p = p.next;
        }
        if (p1 != null) {
            p.next = p1;
        }
        if (p2 != null) {
            p.next = p2;
        }
        return dummy.next;
    }
}