每日一道 LeetCode (7):合并两个有序链表

极客挖掘机

共 1951字,需浏览 4分钟

 ·

2020-08-06 00:00

每天 3 分钟,走上算法的逆袭之路。

前文合集

每日一道 LeetCode 前文合集

代码仓库

GitHub:https://github.com/meteor1993/LeetCode

Gitee:https://gitee.com/inwsy/LeetCode

题目:合并两个有序链表

题目来源:https://leetcode-cn.com/problems/merge-two-sorted-lists/

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

示例:

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

解题方案:迭代

首先需要了解一下链表的数据结构,如果这个不清楚这道题完全没得玩。

我还是先写下定义链表的代码,配合代码好理解一下:

public class ListNode {

public int val;
public ListNode next;

public ListNode() {

}

public ListNode(int val) {
this.val = val;
}

public ListNode (int val, ListNode next) {
this.val = val;
this.next = next;
}
}

这段代码异常简单,定义了一个数据域用来存放一个整数 val ,然后定义了一个指针指向另一个 ListNode ,这就形成了一个单独的链表上的节点。

接下来是排序,我相信如果是两个数组排序大多数人应该都写的出来,实际上链表的排序和数组的排序也差不多,正向思维就是直接循环排序,简单粗暴。

思路简单代码也简单,看下我写的单纯的迭代排序的代码:

// 暴力迭代
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode prehead = new ListNode(-1);

ListNode prev = prehead;

while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
prev.next = l1;
l1 = l1.next;
} else {
prev.next = l2;
l2 = l2.next;
}
prev = prev.next;
}

prev.next = l1 == null ? l2 : l1;

return prehead.next;
}

是不是很简单,判断两个链表节点的大小,然后修改指针的指向,接着循环,循环到两个节点都为 null 为止。

需要注意的是当循环终止的时候, l1 和 l2 最多有一个是非空的,这时候需要在

解题思路:递归

秉承着良好的习惯,做完题以后看下答案,大体排序思路没什么滑头,但是看到了另一种写法,这个写法写起来说实话,还真有点不大会写。

虽然这么说有点丢人,但我就是这么不要脸,就这么直接说出来了,递归这种方式,平时基本不怎么写,突然冷不丁的让我写一下,还是蛮困难的。

// 递归
public ListNode mergeTwoLists_1(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
else if (l2 == null) return l1;
else if (l1.val < l2.val) {
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}

递归的代码看起来是十分简洁的,简洁的代价是可读性降低。

不过话说回来,递归的写法是每一位码农都应该熟悉的,虽然不常用。。。

PS:又找到自己短板了,每天能通过这种方式发现一个短板补一个短板还是很开心的。


感谢阅读



浏览 25
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报
评论
图片
表情
推荐
点赞
评论
收藏
分享

手机扫一扫分享

分享
举报