首页 > 编程语言 > 详细

刷题记录-剑指offer25:合并两个排序的链表

时间:2020-06-02 09:19:51      阅读:62      评论:0      收藏:0      [点我收藏+]

输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

法1:递归

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        if(list1.val>= list2.val){
            list2.next = Merge(list1, list2.next);
            return list2;
        }else{
            list1.next = Merge(list1.next, list2);
            return list1;
        }
    }
}

做了这么多题,总结出一个规律,要用好递归,只需要做到两个步骤,明确递归的功能和返回值、设置好递归的结束条件,然后把函数当成黑箱,不要被绕进去

法2:创建一个新链表,遍历两个链表,把最小值放进新链表

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(1);
        ListNode temp = head;
        while(list1 != null && list2 != null){
            if(list1.val>= list2.val){
                temp.next = list2;
                list2 = list2.next;
            }else{
                temp.next = list1;
                list1 = list1.next;
            }
            temp = temp.next;
        }
        if(list1 == null)
            temp.next = list2;
        if(list2 == null)
            temp.next = list1;
        return head.next;
    }
}

 

刷题记录-剑指offer25:合并两个排序的链表

原文:https://www.cnblogs.com/tendermelon/p/13028864.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!