( Leetcode 21 ) Merge Two Sorted Lists （高效解法）

最新推荐文章于 2024-01-12 14:30:52 发布

__William__

最新推荐文章于 2024-01-12 14:30:52 发布

阅读量6.7k

点赞数

分类专栏： leetcode 文章标签： leetcode linked list java

本文链接：https://blog.csdn.net/willduan1/article/details/51398061

版权

leetcode 专栏收录该内容

35 篇文章

订阅专栏

本文介绍了一种不同于常规思路的合并两个有序链表的方法。该方法以其中一个链表为中心链表，通过交换节点的方式实现合并，同时提供了详细的Java代码实现。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

题目：Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

解题思路：

虽然这道题比较简单，首先人人都能想到最基本的那种解法，即设置两个指针来依次比较。但是下面我说一种完全不同的思路。

首先思路是以链表L1为中心链表，最后返回L1，L2链表是插入到L1链表上面的，总的是靠来回交换两个链表完成的。

1. 比较L1和L2的头结点，如果L1头结点比L2大，那么交换着两个结点

2. 设置p指向L1，依次和L2结点大小比较，如果p的下一个结点比L2结点大，那么将L2的后半段接到L1后面，L1的后半段变成L2链表

3. 重复1 和 2.

其实主要思想就是始终让p指向小的数值的那个链表。

具体看下面的Java代码：

public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
		//最终的返回结果是以l1为中心链，l2往l1上面插结点
        ListNode tmp;
        if (l1.val > l2.val) {   //交换两个头结点
            tmp = l2;
            l2 = l1;
            l1 = tmp;
        }
        ListNode p = l1;
        while (l2 != null) {
            while (p.next != null && p.next.val <= l2.val) 
				p = p.next;
            tmp = p.next;
            p.next = l2;
            l2 = tmp;
        }
        return l1;
    }
}

程序运行之后截图：