本文共 1735 字，大约阅读时间需要 5 分钟。

合并两个已排序的链表是一个常见的问题，目标是将两个链表拼接成一个新的链表，并返回其第一个节点。本文将详细介绍如何实现这一过程。

输入节点情况

首先，我们需要考虑输入链表可能存在null的情况。具体来说：

节点定义

节点的定义如下：

class ListNode {    public int val;    public ListNode next;    public ListNode prev;}

实现步骤

代码实现

public class ListNode {    public int val;    public ListNode next;    public ListNode prev;    public ListNode(int val) {        this.val = val;    }}public class Solution {    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {        // 处理空链表情况        if (l1 == null) {            return l2;        }        if (l2 == null) {            return l1;        }        // 初始化结果链表        ListNode result = new ListNode(0);        ListNode last = result;        // 确定第一个节点        if (l1.val > l2.val) {            // 交换l1和l2的位置            ListNode temp = l1;            l1 = l2;            l2 = temp;        }        // 开始遍历并拼接        while (true) {            // 将当前l1节点连接到结果链表            last.next = l1;            last = last.next;            // 移动l1指针到下一个节点            if (l1.next == null) {                // 当l1遍历完毕，将l2拼接到结果链表                l1.next = l2;                break;            }            l1 = l1.next;            // 比较当前节点的值，并交换位置            if (l1.val > l2.val) {                // 交换l1和l2的位置                ListNode temp = l2;                l2 = l1;                l1 = temp;            }        }        return result.next;    }}

总结

该算法通过交换节点的位置和逐步拼接的方式，确保了两个链表合并后的链表是有序的。代码结构清晰，逻辑简单易懂，适合处理各种边界情况。

转载地址：http://soyyz.baihongyu.com/