合并有序链表_

Java

huangziqiang

import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/

public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here

//方法一：链表-->集合(排序)-->链表
/*
if(l1 == null && l2 == null) return null;

else if(l1 == null && l2 != null) return l2;

else if(l1 != null && l2 == null) return l1;

else{
List<Integer> list = new ArrayList<>();

while(l1 != null){
list.add(l1.val);
l1 = l1.next;
}

while(l2 != null){
list.add(l2.val);
l2 = l2.next;
}

Collections.sort(list);//直接调用Collections工具类的sort()方法，对集合进行排序

ListNode headNode = new ListNode(list.get(0));
ListNode cur = headNode;

for(int i = 1; i < list.size(); i++){
cur.next = new ListNode(list.get(i));
cur = cur.next;
}

return headNode;
}
*/


//方法二：链表循环添加遍历发
/*
if(l1 == null && l2 == null) return null;

else if(l1 == null && l2 != null) return l2;

else if(l1 != null && l2 == null) return l1;

else{
ListNode headNode = new ListNode(0);
//注意：不能ListNode headNode = null;
//否则会报java.lang.NullPointerException
ListNode cur = headNode;

while(l1 != null && l2 != null){

if(l1.val < l2.val){
cur.next = l1;
cur = cur.next;
l1 = l1.next;
}else{
cur.next = l2;
cur = cur.next;
l2 = l2.next;
}
}

if(l1 != null) cur.next = l1;//l1嚯l2中如果有一方先添加完了，就继续添加另一方

if(l2 != null) cur.next = l2;

return headNode.next;//要注意，headNode定义为null了，因此要返回headNode.next
}
*/


//方法三：递归法
if(l1 == null && l2 == null) return null;

else if(l1 == null && l2 != null) return l2;

else if(l1 != null && l2 == null) return l1;

else{
ListNode headNode = null;

if (l1.val < l2.val) {
headNode = l1;
headNode.next = mergeTwoLists(l1.next, l2);
} else {
headNode = l2;
headNode.next = mergeTwoLists(l1, l2.next);
}

return headNode;
}
}
}

发表于 2021-08-02 17:55:42 回复(0)

Java

Aooohan

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        if(l1.val > l2.val) {
            l2.next = mergeTwoLists(l1,l2.next);
            return l2;
        }else{
            l1.next = mergeTwoLists(l1.next,l2);
            return l1;
        }
    }
}

发表于 2021-07-31 19:56:21 回复(0)

Java

TylerChen

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
      
        ListNode head = new ListNode(-1), p = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                p.next = l1;
                l1 = l1.next;
            }else {
                 p.next = l2;
                l2 = l2.next;
            }
            p = p.next;
        }
        if(l1 != null){
            p.next = l1;
        }else {
            p.next = l2;
        }
        return head.next;
       
        
    }
}

发表于 2021-07-27 00:04:31 回复(0)

Java

对喝点水

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if(l1 == null && l2 == null){
            return null;
        }else{
            if(l1 == null){
                return l2;
            }
            if(l2 == null){
                return l1;
            }
        }
        ListNode head = l1;
        ListNode temp = l2;
        if(l1.val <= l2.val){
            head = l1;
            temp = l2;
        }else{
            head= l2;
            temp = l1;
        }
        
        ListNode cur = head.next;
        ListNode resHead = head;
        resHead.next = null;
        while(cur!=null && temp!=null){
            while(cur!=null && temp != null && cur.val <= temp.val){
                resHead.next = cur;
                resHead = resHead.next;
                cur = cur.next;
            }
            while(cur!=null && temp != null && cur.val > temp.val){
                resHead.next = temp;
                resHead = resHead.next;
                temp = temp.next;
            }
        }
        while(cur != null){
            resHead.next = cur;
            resHead = resHead.next;
            cur =cur.next;
        }
        while(temp != null){
            resHead.next = temp;
            resHead = resHead.next;
            temp =temp.next;
        }
        return head;
    }
}

发表于 2021-07-22 10:50:59 回复(0)

Java

shine0801

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode head = new ListNode(0);
        ListNode s = head;
        while(l1 != null && l2 != null){
            if(l1.val<l2.val){
             s.next = l1;
             s = l1;
             l1 = l1.next;
            }
            else{
                s.next = l2;
                s = l2;
                l2 = l2.next;
                }
        }
        
        if(l1!=null)
            s.next = l1;
        if(l2!=null)
            s.next = l2;
        
        return head.next;
    }

发表于 2021-05-30 17:24:45 回复(0)

Java

牛客507555376号

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        
        ListNode head = l1.val<l2.val?l1:l2;
        ListNode cur = head;
        ListNode other = l1.val<l2.val?l2:l1;
        while(cur.next!=null&&other!=null){
            if(cur.next.val<=other.val){
                cur=cur.next;
            }else{
                ListNode tmp = cur.next;
                cur.next = other;
                cur = other;
                other = tmp;
            }
        }
        
        if(cur.next==null&&other!=null){
            cur.next=other;
        }
        
        return head;
    }
}

编辑于 2021-05-16 11:23:21 回复(0)

Java

惠灵顿靖

/*
二刷
思路：
    1.输入问题：考虑为空！
    2.新链表的第一个结点问题，由于一般情况下第一个结点都需要特殊处理，比较实用的解决办法是在第一个结点前增加一个虚拟的头结点(例如下面的head)，
      讲实际的第一个结点一般化。最后输出的时候输出这个虚拟结点的下一个结点就OK
    3.如何为新链表选择下一个结点（已经虚拟出第一个结点了。）这个比较容易，比大小就OK了。取小的并并在此链表前进一步。
    4.注意循环的终止条件！
    5.终止后并没有结束！
*/
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode pre=new ListNode(0);
        ListNode head=pre;
        while(l1!=null&&l2!=null){
            if(l1.val<=l2.val){
                head.next=l1;
                head=head.next;
                l1=l1.next;
            }
            else{
                head.next=l2;
                head=head.next;
                l2=l2.next;
            }
        }
        while(l1==null&&l2!=null){
            head.next=l2;
            head=head.next;
            l2=l2.next;
        }
        while(l2==null&&l1!=null){
            head.next=l1;
            head=head.next;
            l1=l1.next;
        }
        return pre.next;
}}

发表于 2021-04-25 22:57:26 回复(0)

Java

-SoFar°

 public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //和数组法一样的解法
        //合并有序链表 和合并有序数组思想是一致的
        //双指针不停找到两个链表中的较小的那个 然后加入哑巴节点为头的链表
        //哑巴节点方便处理边界问题
        //这种合并有序题 不管是数组还是链表 都是双指针套路 因为初态有序。
        //不直接操作链表 而是使用的引用
        ListNode p=l1,q=l2,dumbNode=new ListNode(-1);
        ListNode temp = dumbNode;//temp是用来形成结果链表的
        while (p!=null&&q!=null){
            if (p.val<=q.val){//如果p小 那么让temp.next指向p
                temp.next = p;
                p = p.next;//p后移
            }else if (p.val>q.val){//如果q小 那么让temp.next指向q
                temp.next=q;
                q=q.next;
            }
            temp =temp.next;//非常关键！！ temp光指定next还不够 还得去自己的next
            //这样才是迭代
        }
        //出循环 代表 l1和l2至少有一个已经走完了 或者天然的 一个为空链表
        //也就是说 还要处理剩下没被处理的的节点
        //如果l1为空 那么意味着l2里剩下的节点要全部直接给temp.next
        //同理如果l1不为空 那l2为空的话 把剩下的l1加到temp.next
        //如果都空 那么temp.next = null
        temp.next=(p==null)?q:p;
        return dumbNode.next;
    }

编辑于 2021-03-06 05:58:22 回复(0)

Java

匿迹小王子

    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // 特殊情况处理
        if (l1 == null && l2 == null) {
            return null;
        }

        if (l1 == null) {
            return l2;
        }

        if (l2 == null) {
            return l1;
        }

        // 一次归并操作
        ListNode dummyNode = new ListNode(-1);
        ListNode current = dummyNode;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                current.next = l1;
                l1 = l1.next;
            } else {
                current.next = l2;
                l2 = l2.next;
            }

            current = current.next;
        }

        if (l1 != null) {
            current.next = l1;
        }

        if (l2 != null) {
            current.next = l2;
        }


        return dummyNode.next;
    }

发表于 2021-02-28 12:32:47 回复(0)

Java

花落梦里

    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        //递归的思想
        if(l1==null) return l2;
        if(l2==null) return l1;
        ListNode node = null;
        if(l1.val<l2.val){
            node=l1;
            node.next=mergeTwoLists(l1.next,l2);
        }
        else{
            node=l2;
            node.next=mergeTwoLists(l1,l2.next);
        }
              
        return node;
    }

发表于 2021-01-28 08:33:47 回复(0)

Java

淡然处之_

//话不多说，这道题应该比较简单，依次比较哪个元素小，就插入到新的链表后面，记得要向前移动，不要断链。最后还有判断两个合并的链表是否已经都遍历完了。

public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode p1 = l1;
        ListNode p2 = l2;
        ListNode l = new ListNode(6);
        l.next = null;
        ListNode q = l;
        while(p1!=null&&p2!=null){
            if(p1.val<=p2.val){
                q.next=p1;
                q = q.next;
                p1 = p1.next;
                q.next=null;
            }else if(p1.val>p2.val){
                q.next=p2;
                q=q.next;
                p2=p2.next;
                q.next=null;
            }
        }
        while(p1!=null){
            q.next=p1;
            p1=p1.next;
            q=q.next;
        }
        while(p2!=null){
            q.next=p2;
            p2=p2.next;
            q=q.next;
        }
        q.next=null;
        return l.next;
    }

发表于 2021-01-05 18:03:13 回复(0)

Java

执子一白

这道题说起来还蛮简单的
总体的思想就是归并排序合并的思想，包括 l1 l2 已经有序所以只需要有序比对合并即可。
注意边界条件及一些临时指针即可

import java.util.*;
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        if(l1==null&&l2==null){
            return null;
        }
        if(l1!=null&&l2==null){
            return l1;
        }
        if(l1==null&&l2!=null){
            return l2;
        }
        //初始化新链表头节点 这里注意 l1 l2 为有序 类似归并排序
        ListNode resultNodeHead=null;
        if(l1.val<l2.val){
            resultNodeHead=l1;
            l1=l1.next;
        }else{
            resultNodeHead=l2;
            l2=l2.next;
        }
        ListNode tmpNode=resultNodeHead;
        while(l1!=null&&l2!=null){
            if(l1.val<l2.val){
              tmpNode.next=l1;
              l1=l1.next;
            }else{
              tmpNode.next=l2;
              l2=l2.next;
            }
            tmpNode=tmpNode.next;
        }
        while(l1!=null){
            tmpNode.next=l1;
            l1=l1.next;
            tmpNode=tmpNode.next;
        }
        while(l2!=null){
            tmpNode.next=l2;
            l2=l2.next;
            tmpNode=tmpNode.next;
        }
        return resultNodeHead;
    }
}

图片说明

思考了一下最后两个 while 没什么必要了，因为是有序链表所以直接指向就可以了

        if(l1!=null){
            tmpNode.next=l1;
        }
        if(l2!=null){
            tmpNode.next=l2;
        }

编辑于 2020-11-28 12:01:58 回复(0)

Java

tornado123

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode node = head;
        while(l1 != null && l2 != null) {
            if(l1.val <= l2.val) {
                node.next = l1;
                l1 = l1.next;
            }else {
                node.next = l2;
                l2 = l2.next;
            }
            node = node.next;
        }
        if(l1 != null) {
            node.next = l1;
        }
        if(l2 != null) {
            node.next = l2;
        }
        return head.next;
    }
}

发表于 2020-11-15 01:05:49 回复(0)

Java

编程到死眼aaa

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        ListNode dum = new ListNode(0),cur = dum;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                cur.next = l1;
                l1 = l1.next;
            }else{
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        cur.next = l1 != null ? l1:l2;
        return dum.next;
    }
}

思路：伪造零时节点dum,比较l1和l2的大小，谁小每次就把cur.next等于谁。无论谁大谁小每次都把cur置为cur.next，也就是l1,l2中的较小者。最后是三目运算判断。

发表于 2020-10-31 19:24:53 回复(0)

Java

月关雨辰

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        
        if(l1 == null){
            return l2;
        }
        
        if(l2 == null){
            return l1;
        }
        
        ListNode head = new ListNode(-1);
        ListNode headTemp = head;
        ListNode node1 = l1;
        ListNode node2 = l2;
        
        while(node1!=null && node2!=null){
            
            //2个链表中含重复元素
            if(node1.val <= node2.val){
                head.next = node1;
                head = node1;
                node1 = node1.next;
            }else if(node1.val > node2.val){
                head.next = node2;
                head = node2;
                node2 = node2.next;
            }
        }
        
        //链表1长度>链表2长度 链表2遍历完了
        if(node1!=null){
            head.next = node1;
        }
        
        //链表1长度<链表2长度 链表1遍历完了
        if(node2!=null){
            head.next = node2;
        }
        
        return headTemp.next;
    }
}

编辑于 2021-01-17 01:58:56 回复(0)

Java

MASON666

import java.util.*;

/*
* public class ListNode {
* int val;
* ListNode next = null;
* }
*/

public class Solution {
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
// write code here
ListNode ln = new ListNode(0);
ListNode p=l1,q=l2;
if(p==null)return q;
if(q==null)return p;
if(p.val>q.val){
ln = q;
ln.next=mergeTwoLists(q.next,p);
}else{
ln=p;
ln.next=mergeTwoLists(q,p.next);
}
return ln;
}

}

递归冲

发表于 2020-09-15 19:27:27 回复(0)

Java

一杯二锅头

通过递归方式，减少对象创建，递归可以使next节点交替进行

public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
ListNode res = new ListNode(-1);
merge(l1, l2, res);
return res.next;
}

private void merge(ListNode l1, ListNode l2, ListNode m) {
if (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
m.next = l1;
merge(l1.next, l2, m.next);
} else {
m.next = l2;
merge(l1, l2.next, m.next);
}
}
if (l1 == null) {
m.next = l2;
}
if (l2 == null) {
m.next = l1;
}
}

发表于 2020-09-09 01:51:58 回复(0)

Java

乱石穿空

我吐了，同样的代码，通不过。难道是我注释写多了??有大佬帮我看看吗？

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {//
        // write code here
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode newHead = new ListNode(-1);
        ListNode cur = newHead;
        //考虑升序还是降序，先升序把
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                //l1小，先将l1插入新链表末尾
                cur.next = l1;
                //l1进入后，更新l1
                l1 = l1.next;
            } else{
                cur.next = l1;
                l2 = l2.next;
            }
            //更新cur
            cur = cur.next;
        }
        //循环结束，l1或者l2可能为空，应该继续拼接
        cur.next = l1 != null ? l1 : l2;
        //最后将无意义头节点删除
        return newHead.next;
    }
}

发表于 2020-09-07 11:24:31 回复(1)

Java

GTboy

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */
// 思路：递归
public class Solution {
    /**
     * 
     * @param l1 ListNode类 
     * @param l2 ListNode类 
     * @return ListNode类
     */
    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;
        }
    }
}

编辑于 2020-09-01 11:11:33 回复(0)

Java

牛客589533603号

public class Solution {
    public ListNode mergeTwoLists (ListNode l1, ListNode l2) {
        // write code here
        //判断空
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        //新建节点保存
        ListNode newNode = new ListNode(0);//重点，需要初始化头节点
        ListNode node = newNode;
        while(l1!=null && l2!=null){
            if(l1.val < l2.val){
                newNode.next = l1;
                l1 = l1.next;
            }
            else{
                newNode.next = l2;
                l2 = l2.next;
            }
            newNode = newNode.next;
        }
        if(l1 != null)
            newNode.next = l1;
        else
            newNode.next = l2;
        return node.next; //返回头节点下一个
    }
}

发表于 2020-08-29 15:17:04 回复(0)

合并有序链表

输入

输出

输入

输出

输入

输出

说明：本题目包含复杂数据结构ListNode，点此查看相关信息

问题信息

热门推荐

通过挑战的用户

相关试题