【力扣】21.合并两个有序链表
2023-12-13 05:44:27
?21.合并两个有序链表
生活真的是不容易啊,我感觉刷题就是正视智商的过程。它视我为渣渣,我视它为大腿。必须练!必须坚持!爬坡哪有不辛苦的啊~
虽然这个力扣上面的这个题目标注的是简单,simple,可是我觉得在递归上面是一点也不简单,哼!(我好笨,呜呜呜~)
方法一:暴力解法(迭代法)
题解:用一个辅助结点。然后比较两链表此时的结点值。看代码吧
代码如下:
/**
* 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 list1, ListNode list2) {
//1.迭代法。用一个指针来维护和判断,并进行连接。amazing!
ListNode prehead=new ListNode(-1);
ListNode prev=prehead;
while(list1!=null&&list2!=null){
if(list1.val<=list2.val){
prev.next=list1;
list1=list1.next;
}else{
prev.next=list2;
list2=list2.next;
}
prev=prev.next;
}
prev.next=list1==null?list2:list1;
return prehead.next;
}
}
方法二:递归
我知道你可能觉得很简单,可对于一个差不多是小白的而言,搞懂这个原理是折磨,是欲哭无泪,是心酸...
首先,我的问题就在于没搞懂它所返回的值,让我有点懵。你要知道,递归完之后,是要回溯的!且必须!。所以在递归完之后,根据其返回的结果对其进行一个整理,最后进行返回即可。
那返回的结果给到哪呢,给到函数mergeTwoLists(x,x)呀,家人,然后再执行。
这里说一下代码执行的这个流程,说完之后再想想估计你就明白了。
- 首先先判断两条链表是否为空,也要判断在其递归的过程中是否走到了尽头。因为这l1和l2两个指针是在不断移动的。
- 若不为空,则比较此时两条链表中元素值的大小,因为是根据这个在往下递归。继续调用自己的函数,并重复直到两天链表中有一条为空。
- 然后将返回的值给l1.next或者l2.next,并将此时的l1或者l2返回给上一级的1.next或者l2.next实现一个链表的重组,直到回溯结束为止。我这里有个图片,你可以看看,就是有点潦草。
代码如下:
/**
* 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) {
if(l1==null) return l2;
if(l2==null) return l1;
if(l1.val<l2.val){
l1.next=mergeTwoLists(l1.next,l2);
return l1;
}else{
l2.next=mergeTwoLists(l1,l2.next);
return l2;
}
}
}
祝你刷题快乐~
文章来源:https://blog.csdn.net/qq_62649563/article/details/134952468
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!