LeetCode第21题合并两个有序链表

简介: 该文章介绍了 LeetCode 第 21 题合并两个有序链表的解法,通过创建新链表,依次比较两个链表的头节点值,将较小的值插入新链表,直至其中一个链表遍历完,再将另一个链表剩余部分接到新链表后面,实现合并。

继续打卡算法题,今天学习的是LeetCode的第21题合并两个有序链表,这道题目是道简单题。算法题的一些解题思路和技巧真的非常巧妙,每天看一看算法题和解题思路,我相信对我们的编码思维和编码能力有一些帮助。

image.png

分析一波题目

看完题目,很容易想到构建一个新链表,然后每次遍历两个链表并找一个最小的节点作为新链表的节点,直到两个链表都遍历到了尾。这样需要记录两个链表遍历到的指针,这样会涉及到多个指针的变化,非常复杂了。

如果我们使用递归就可以避免这种多个指针的控制,只要控制递归结束条件就可以。

但是递归思想真的是非常不好讲清楚!!直接上代码

image.png

编码解决

/**
 * 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 l1, ListNode l2) {
   
   
        //l1到达了尾部
        if (l1 == null) {
   
   
            return l2;
        }
        //l2到达了尾部
        else if (l2 == null) {
   
   
            return l1;
        }
        //节点判断 l1作为头节点
        else if (l1.val < l2.val) {
   
   
            //找l1的下一个节点
            l1.next = mergeTwoLists(l1.next, l2);
            //返回l1,成为上一个节点的next
            return l1;
        }
        //节点判断 l2作为头节点
        else {
   
   
            //重新找l2的下一个节点
            l2.next = mergeTwoLists(l1, l2.next);
            //返回l2,成为上一个节点的next
            return l2;
        }

    }
}

总结

递归对于解决嵌套循环多次的情况比较巧妙,但是递归很难讲清楚,我们可以举简单的数据例子,套入递归代码,这样就容易理解。

相关文章
|
2月前
|
索引 Python
【Leetcode刷题Python】328. 奇偶链表
在不使用额外空间的情况下,将链表中的奇数和偶数索引节点重新排序的方法,并提供了相应的Python实现代码。
30 0
|
2月前
|
Python
【Leetcode刷题Python】25.K 个一组翻转链表
解决LeetCode "K 个一组翻转链表" 问题的三种方法:使用栈、尾插法和虚拟节点顺序法,并提供了每种方法的Python实现代码。
28 0
|
2月前
|
算法
LeetCode第24题两两交换链表中的节点
这篇文章介绍了LeetCode第24题"两两交换链表中的节点"的解题方法,通过使用虚拟节点和前驱节点技巧,实现了链表中相邻节点的交换。
LeetCode第24题两两交换链表中的节点
|
2月前
|
存储 算法
LeetCode第86题分隔链表
文章介绍了LeetCode第86题"分隔链表"的解法,通过创建两个新链表分别存储小于和大于等于给定值x的节点,然后合并这两个链表来解决问题,提供了一种简单易懂且操作原链表的解决方案。
LeetCode第86题分隔链表
|
2月前
|
存储 算法
LeetCode第83题删除排序链表中的重复元素
文章介绍了LeetCode第83题"删除排序链表中的重复元素"的解法,使用双指针技术在原链表上原地删除重复元素,提供了一种时间和空间效率都较高的解决方案。
LeetCode第83题删除排序链表中的重复元素
|
2月前
|
算法
LeetCode第23题合并 K 个升序链表
这篇文章介绍了LeetCode第23题"合并K个升序链表"的解题方法,使用分而治之的思想,通过递归合并链表的方式解决了这个难题。
LeetCode第23题合并 K 个升序链表
|
2月前
|
Python
【Leetcode刷题Python】114. 二叉树展开为链表
LeetCode上114号问题"二叉树展开为链表"的Python实现,通过先序遍历二叉树并调整节点的左右指针,将二叉树转换为先序遍历顺序的单链表。
24 3
【Leetcode刷题Python】114. 二叉树展开为链表
|
2月前
|
C++ 索引
leetcode 707.设计链表
本文提供了解决LeetCode 707题"设计链表"的C++实现,包括单链表的节点定义和类方法实现,如添加节点、获取节点值、删除节点等。
|
2月前
|
算法
LeetCode第92题反转链表 II
文章分享了LeetCode第92题"反转链表 II"的解法,通过使用四个指针来记录和更新反转链表段的头部、尾部以及前一个和后一个节点,提供了一种清晰且易于理解的解决方案。
LeetCode第92题反转链表 II
|
2月前
|
算法
LeetCode第19题删除链表的倒数第 N 个结点
该文章介绍了 LeetCode 第 19 题删除链表的倒数第 N 个结点的解法,通过使用快慢双指针,先将快指针移动 n 步,然后快慢指针一起遍历,直到快指针到达链尾,从而找到倒数第 N 个结点的前一个结点进行删除,同时总结了快慢指针可减少链表遍历次数的特点。
LeetCode第19题删除链表的倒数第 N 个结点