Java教程

剑指 Offer 25. 合并两个排序的链表(简单)

本文主要是介绍剑指 Offer 25. 合并两个排序的链表(简单),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

通过率 72.9%

题目链接

题目描述:

输入两个递增排序的链表,合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1:

输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4

限制:

0 <= 链表长度 <= 1000

思路:

类似归并排序,设双指针分别指向l1和l2,根据节点值的大小来判断节点添加顺序,不过有个细节要注意(看官网精选题解):

  • 头节点的确定:一开始我只想到先判断l1和l2的头节点大小,从而将头节点小的那个作为res返回结果的头节点,也是看了Krahets大神的题解才知道还有引入伪头节点这个方法,这样就不用特判l1和l2的头节点了,最后返回res.next就行了,秒啊

另外,当l1或l2为空跳出合并循环时,可以直接用三元表达式判断将哪个添加到末尾,以节省代码量

 1 /*JavaScript*/
 2 /**
 3  * Definition for singly-linked list.
 4  * function ListNode(val) {
 5  *     this.val = val;
 6  *     this.next = null;
 7  * }
 8  */
 9 /**
10  * @param {ListNode} l1
11  * @param {ListNode} l2
12  * @return {ListNode}
13  */
14 var mergeTwoLists = function(l1, l2) {
15     const res = new ListNode(0)
16     let p = res
17     while(l1 && l2) {
18         if(l1.val <= l2.val) {
19             p.next = l1
20             l1 = l1.next
21         } else {
22             p.next = l2
23             l2 = l2.next
24         }
25         p = p.next
26     }
27     p.next = l1 ? l1 : l2
28     return res.next
29 };

 

这篇关于剑指 Offer 25. 合并两个排序的链表(简单)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!