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月前
【力扣】-- 移除链表元素
【力扣】-- 移除链表元素
38 1
|
2月前
Leetcode第21题(合并两个有序链表)
这篇文章介绍了如何使用非递归和递归方法解决LeetCode第21题,即合并两个有序链表的问题。
52 0
Leetcode第21题(合并两个有序链表)
|
2月前
|
存储 算法
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
【❤️算法笔记❤️】-每日一刷-21、合并两个有序链表
108 0
|
2月前
LeetCode第二十四题(两两交换链表中的节点)
这篇文章介绍了LeetCode第24题的解法,即如何通过使用三个指针(preNode, curNode, curNextNode)来两两交换链表中的节点,并提供了详细的代码实现。
25 0
LeetCode第二十四题(两两交换链表中的节点)
|
2月前
Leetcode第十九题(删除链表的倒数第N个节点)
LeetCode第19题要求删除链表的倒数第N个节点,可以通过快慢指针法在一次遍历中实现。
45 0
Leetcode第十九题(删除链表的倒数第N个节点)
|
2月前
|
索引
力扣(LeetCode)数据结构练习题(3)------链表
力扣(LeetCode)数据结构练习题(3)------链表
96 0
|
2月前
【LeetCode 10】142. 环形链表 II
【LeetCode 10】142. 环形链表 II
23 0
|
2月前
【LeetCode 09】19 删除链表的倒数第 N 个结点
【LeetCode 09】19 删除链表的倒数第 N 个结点
18 0
|
2月前
【LeetCode 08】206 反转链表
【LeetCode 08】206 反转链表
13 0
|
2月前
【LeetCode 06】203.移除链表元素
【LeetCode 06】203.移除链表元素
33 0