【剑指offer】合并两个排序的链表

深碍√TFBOYSˉ_ 2022-04-03 07:59 186阅读 0赞

# 合并两个排序的链表 #

## 题目描述 ##

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

## AC代码 ##

*  递归版本

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    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){
        
                list1.next = Merge(list1.next,list2);
                return list1;
            }else {
        
                list2.next = Merge(list1,list2.next);
                return list2;
            }
        }
    }

*  非递归版本

/*
    public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }*/
    public class Solution {
        
        public ListNode Merge(ListNode list1,ListNode list2) {
        
            if(list1 == null)
                return list2;
            if(list2 == null)
                return list1;
            ListNode mergeHead = null;
            ListNode current = null;
            while(list1 != null && list2 != null){
        
                if(list1.val <= list2.val){
        
                    if(mergeHead == null){
        
                        mergeHead = current = list1;
                    }else{
        
                        current.next = list1;
                        current = current.next;
                    }
                    list1 = list1.next;
                }else{
        
                    if(mergeHead == null){
        
                        mergeHead = current = list2;
                    }else{
        
                        current.next = list2;
                        current = current.next;
                    }
                    list2 = list2.next;
                }
            }
            if(list1 == null)
                current.next = list2;
            if(list2 == null)
                current.next = list1;
            return mergeHead;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，186人围观）

还没有评论，来说两句吧...

相关阅读

相关【剑指offer】——合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。思路：分别比较两个链表listNode1和listNode2

淩亂°似流年/ 2023年08月17日 16:50/ 0 赞/ 91 阅读

相关剑指Offer-合并两个排序的链表

合并两个排序的链表题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。解题思路：其实就是采用

绝地灬酷狼/ 2022年08月04日 12:50/ 0 赞/ 139 阅读

相关剑指Offer | 合并两个排序的链表

做了个剑指Offer的题目目录，链接如下： [https://blog.csdn.net/mengmengdastyle/article/details/80317246]

怼烎@/ 2022年05月24日 04:37/ 0 赞/ 155 阅读

相关剑指offer:合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 AC C++ Solution: class Solu

Myth丶恋晨/ 2022年04月10日 07:54/ 0 赞/ 208 阅读

相关【剑指offer】合并两个排序的链表

合并两个排序的链表题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 AC代码递归版本

深碍√TFBOYSˉ_/ 2022年04月03日 07:59/ 0 赞/ 187 阅读

相关剑指Offer-合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。初步解题思路：新建一个链表，用来顺序存储list1和list2。

女爷i/ 2022年02月27日 01:06/ 0 赞/ 207 阅读

相关剑指offer|合并两个排序的链表

【题目描述】输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。时间限制：1秒空间限制：32768K 热度指数：446096

拼搏现实的明天。/ 2022年02月16日 15:10/ 0 赞/ 196 阅读

相关剑指offer-合并两个排序的链表

题目描述输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。算法思想合并两个有序的链表非常的简单。首先申请一个

- 日理万妓/ 2022年02月13日 11:13/ 0 赞/ 248 阅读

相关剑指Offer——合并两个排序的链表

1、题目描述　　输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 2、代码实现 1 package com.baoz

约定不等于承诺〃/ 2021年12月03日 21:17/ 0 赞/ 257 阅读

相关剑指offer：合并两个排序的链表

试题：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。代码：典型的[归并算法][Link 1]。 /

桃扇骨/ 2021年09月16日 15:46/ 0 赞/ 296 阅读