首页 > 试题广场 > 合并两个排序的链表
[编程题]合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null)
            return list2;
        if(list2 == null)
            return list1;
        ListNode resultNode = null;
        if(list1.val < list2.val){
            resultNode = list1;
            resultNode.next = Merge(list1.next,list2);
        }
        else{
            resultNode = list2;
            resultNode.next = Merge(list1,list2.next);
        }
        return resultNode;
    }
}

发表于 2019-08-18 15:42:02 回复(0)
非递归
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //进行判空
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        //制造哑节点
        ListNode dumNode=new ListNode(0);
        dumNode.next=list1;
        //指向第一个链表的当前元素的前一个元素的指针
        ListNode pre=dumNode;
        //创建两个指针用于遍历两个链表
        ListNode head1=list1;
        ListNode head2=list2;
        //指向第二个链表的当前元素的后一个元素的指针
        ListNode next=null;
        while(head1!=null && head2!=null){
            //假如第一个链表的a大于第二个链表的b,则把第二个链表的b插入a之前
            if (head1.val>=head2.val){
                //防止链表断开
                next=head2.next;
                //将节点head2加入第一个链表
                head2.next=pre.next;
                pre.next=head2;
                //第二个链表往后推,第一个链表pre往后推
                pre=pre.next;
                head2=next;
            }else{
                //假如第一个链表的a小于第二个链表的b,则第一链表的元素往后推
                //第二次接着比大小
                head1=head1.next;
                pre=pre.next;
            }
        }
        //如果list2不为空
        if (head2!=null){
            //把链表2全部加到链表1
            pre.next=head2;
        }
        return dumNode.next;
}
}
发表于 2019-08-08 21:26:15 回复(0)

    /*以下代码基本思路是通过创建新的链表实现,只涉及三个链表*/
    /*还可以选取长度较小的链表,将小链表的值添加到大链表中,使用其中一个链表完成功能,只涉及两个链表*/
    /*此题牛客网的测试用例是输入和输出的链表头节点都含有数据*/
    /*头节点无数据做法*/
    public static ListNode Merge(ListNode list1,ListNode list2) {
        
        if(list1==null)return list2;
        if(list2==null)return list1;
        ListNode list3=new ListNode(0);
        ListNode curr1=list1.next;
        ListNode curr2=list2.next;
        ListNode curr3=list3;
        while(curr1!=null&&curr2!=null) {
             
            while(curr1!=null&&curr2!=null&&curr1.val<=curr2.val ) {
                ListNode tmpListNode=new ListNode(curr1.val);
                tmpListNode.next=null;
                curr3.next=tmpListNode;
                curr3=curr3.next;
                curr1=curr1.next;
            }
            while(curr1!=null&&curr2!=null&&curr2.val<=curr1.val) {
                ListNode tmpListNode=new ListNode(curr2.val);
                tmpListNode.next=null;
                curr3.next=tmpListNode;
                curr3=curr3.next;
                curr2=curr2.next;
            }
        }
        
        while(curr1!=null) {
            ListNode tmpListNode=new ListNode(curr1.val);
                tmpListNode.next=null;
                curr3.next=tmpListNode;
                curr3=curr3.next;
                curr1=curr1.next;
        }
        while(curr2!=null) {
            ListNode tmpListNode=new ListNode(curr2.val);
                tmpListNode.next=null;
                curr3.next=tmpListNode;
                curr3=curr3.next;
                curr2=curr2.next;
        }
        return list3;
        
    }
    /*头节点有数据做法*/
    public static ListNode Merge1(ListNode list1,ListNode list2) {
        if(list1==null)return list2;
        if(list2==null)return list1;
        ListNode list3=null;
        ListNode curr3=null;
        ListNode curr1=list1;
        ListNode curr2=list2;
        while(curr1!=null&&curr2!=null) {
         
            while(curr1!=null&&curr2!=null&&curr1.val<=curr2.val ) {
                ListNode tmpListNode=new ListNode(curr1.val);
                tmpListNode.next=null;
                if(list3==null) {
                    list3=tmpListNode;
                    curr3=list3;
                }else {
                    curr3.next=tmpListNode;
                    curr3=curr3.next;
                }
                
                
                curr1=curr1.next;
            }
            while(curr1!=null&&curr2!=null&&curr2.val<=curr1.val) {
                ListNode tmpListNode=new ListNode(curr2.val);
                tmpListNode.next=null;
                if(list3==null) {
                    list3=tmpListNode;
                    curr3=list3;
                }else {
                    curr3.next=tmpListNode;
                    curr3=curr3.next;
                }
                curr2=curr2.next;
            }
        }
        
        while(curr1!=null) {
            ListNode tmpListNode=new ListNode(curr1.val);
                tmpListNode.next=null;
                if(list3==null) {
                    list3=tmpListNode;
                    curr3=list3;
                }else {
                    curr3.next=tmpListNode;
                    curr3=curr3.next;
                }
                curr1=curr1.next;
        }
        while(curr2!=null) {
            ListNode tmpListNode=new ListNode(curr2.val);
                tmpListNode.next=null;
                if(list3==null) {
                    list3=tmpListNode;
                    curr3=list3;
                }else {
                    curr3.next=tmpListNode;
                    curr3=curr3.next;
                }
                curr2=curr2.next;
        }
        return list3;
                
    }
     
    
    /*以下为测试,测试的是第二种头节点含有数据*/
            public static void main(String[] args) {
                
                ListNode headListNode1=null;
                ListNode curr1=null;
                for (int i = 0; i < 6; i++) {
                    if(i==1||i==3||i==5) {
                        if(headListNode1==null) {
                            headListNode1=new ListNode(i);
                            headListNode1.next=null;
                            curr1=headListNode1;
                        }else {
                            curr1.next=new ListNode(i);
                            curr1=curr1.next;
                        }
                        
                    }
                    
                }
                ListNode headListNode2=null;
                ListNode curr2=null;
                for (int i = 0; i <= 6; i++) {
                    if(i==2||i==4||i==6) {
                        if(headListNode2==null) {
                            headListNode2=new ListNode(i);
                            headListNode2.next=null;
                            curr2=headListNode2;
                        }else {
                            curr2.next=new ListNode(i);
                            curr2=curr2.next;
                        }
                    }
                    
                }
         
        System.out.println("==================================");
          ListNode llListNode=Merge1(headListNode1,headListNode2);
           
          while(llListNode!=null) { 
               System.out.println(llListNode.val);
          llListNode=llListNode.next; }
         
            }
发表于 2019-07-28 17:06:06 回复(0)
/*
基本思路:
思路1:循环
思路2:递归
感觉还是递归比较有趣。

递归思路:
  两个链表list1,list2.分别设置两个引用p1,p2,指向该两个链表头结点。
   若p1小于p2,则将其加入新链表,并将其后续部分与p2合并,反之亦然
*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null)
            return null;
                     
        if(list1 == null)
            return list2;

        if(list2 == null)
            return list1;
                
        ListNode  head ;
        if(list1.val < list2.val){
            head = list1;
            head.next = Merge(list1.next,list2);
        }else{
            head = list2;
            head.next = Merge(list1,list2.next);
        }
        return head;
    }
}

发表于 2019-07-24 10:12:13 回复(0)

我也是新建一个节点去合并两个链表:

public static ListNode Merge(ListNode list1, ListNode list2) {
        ListNode mergeList = new ListNode(0);
        ListNode mergeTemp = mergeList;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                mergeList.next = list2;
                list2 = list2.next;
            } else {
                mergeList.next = list1;
                list1 = list1.next;
            }
            mergeList = mergeList.next;
        }
        if (list1 != null) mergeList.next = list1;
        else if (list2 != null) mergeList.next = list2;
        return mergeTemp.next;
    }
编辑于 2019-07-18 09:46:36 回复(0)
作为一个好的程序员来说,思维比做对这道题更重要,因此我想了以下几种解题方法:
解法一:递归   23 ms
/*
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;
        }
    }
}

解法二:按照常规解题思路来写  21 ms
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
                //需要判断:两个链表是否有空的
        //循环比较,剩下多的直接插入新链表尾部
        //新链表的创建:需要一个新的头结点即可,
        //临时节点p
        //           不要忘了尾结点.next = null
        ListNode head = new ListNode(-1);
        ListNode node = head;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                node.next = list1;
                list1 = list1.next;
            }
            else{
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
        while(list1 != null){
            node.next = list1;
            list1 = list1.next;
            node = node.next;
        }
         while(list2 != null){
            node.next = list2;
            list2 = list2.next;
            node = node.next;
        }
        node.next = null;
        return head.next;
    }
}

解法三:是我通过题目后,看讨论区后对自己解法二的部分优化,
但不知道为什么运行时间却比解法二长     27 ms
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
                //需要判断:两个链表是否有空的
        //循环比较,剩下多的直接插入新链表尾部
        //新链表的创建:需要一个新的头结点即可,
        //临时节点p
        //           不要忘了尾结点.next = null
        ListNode head = new ListNode(-1);
        ListNode node = head;
        while(list1 != null && list2 != null){
            if(list1.val <= list2.val){
                node.next = list1;
                list1 = list1.next;
            }
            else{
                node.next = list2;
                list2 = list2.next;
            }
            node = node.next;
        }
/*      后续发现这段代码可以简化:
            因为不管是list1还是list2提前结束了,
            其另一个都不需要再比较了,
            直接加到尾部就可以
         while(list1 != null){
            node.next = list1;
            list1 = list1.next;
            node = node.next;
        }
         while(list2 != null){
            node.next = list2;
            list2 = list2.next;
            node = node.next;
        }
*/
       //修改后的精简代码:
        if(list1 != null){
            node.next = list1;
        }
        if(list2 != null){
            node.next = list2;
        }
        //同时要去掉后面这行代码
        //node.next = null;
        return head.next;
    }
}
发表于 2019-07-15 22:18:48 回复(0)

用递归方法,首先保证两个链表不为空,为空时连接其实就是返回那个不为空的表。任意取一个链表作为最后的结果链表,将另一个链表的结点插入这个连边。比较list1和list2的数据大小,list1.val>=list2.val,则list2插入到list1,并更新list1指向插入的结点,list1.next指向Merge(list1.next,list2.next),如果list1.val<list2.val,则list1.next指向Merge(list1.next,list2)

    /**
     * 合并链表
     * @param list1
     * @param list2
     * @return  */
    public static ListNode Merge(ListNode list1,ListNode list2){
        if (list1==null&&list2==null){
            return null;
        }
        if (list1==null){
            return list2;
        }
        if (list2==null){
            return list1;
        }
        if (list1.val>=list2.val){
            ListNode cur = list2;
            list2 = list2.next;
            cur.next = list1;
            list1 = cur;
            list1.next = Merge(list1.next,list2);
        }
        else {
            list1.next = Merge(list1.next,list2);
        }
        return list1;
    }

编辑于 2019-07-13 13:36:30 回复(0)
 public ListNode Merge(ListNode list1,ListNode list2) {
    ArrayList<Integer> arrayList = new ArrayList<>(); if (list1 == null && list2 == null) { return null;
    } else if(list1 == null) { return list2;
    } else if (list2 == null) { return list1;
    }
    arrayList.add(list1.val); while(list1.next != null) {
        list1 = list1.next;
        arrayList.add(list1.val);
    }
    arrayList.add(list2.val); while(list2.next != null) {
        list2 = list2.next;
        arrayList.add(list2.val);
    }
    Collections.sort(arrayList);
    ListNode head = new ListNode(arrayList.get(0));
    ListNode result = head; for (int i = 1; i < arrayList.size(); i++) {
        ListNode next = new ListNode(arrayList.get(i));
        head.next = next;
        head = head.next;
    } return result;
}
将每个node的val加到arraylist中,使用Collections.sort(list)进行简单的升序排序。
然后遍历arraylist根据下标进行next结点赋值即可。
发表于 2019-07-11 16:50:25 回复(0)

非递归

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null)
            return list2;
        if (list2 == null)
            return list1;

        ListNode retNode = list1.val <= list2.val ? list1: list2;
        while (list1 != null && list2 != null) {
            ListNode next1 = list1.next;
            ListNode next2 = list2.next;
            if (list1.val <= list2.val) {
                list1.next = list2;
                list1 = next1;
            } 
            else {
                list2.next = list1;
                list2 = next2;
            }
        }

        return retNode;
    }
}

递归

    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;
        }
    }
发表于 2019-06-26 20:14:46 回复(0)
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //递归思想,合并是从两个链表的头节点开始的,如1,3,5,7和2,4,6,8两个链表
        //第一次比较:比较头节点,则list1头节点作为合并后链表的头节点,表一list1不再参加比较
        //第二次比较:表一下一个节点(list1.next)与表二头节点(list2)的比较,小的为头节点
        //依次类推,可以通过递归完成相关逻辑,每一次递归的头节点其实是上一次的头节点的后续节点
            if(list1 == null)return list2;
            if(list2 == null)return list1;
            ListNode head = null;
            if(list1.val <= list2.val){
                    head = list1;
                    head.next = Merge(list1.next, list2);
            }else{
                    head = list2;
                    head.next = Merge(list1, list2.next);
            }
            return head;
    }
}
发表于 2019-05-24 17:20:31 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        if(list1==null&&list2==null){
            return null;
        }
        ListNode newList=null;
        ListNode p=null;
        if(list1.val<list2.val){
            newList=list1;
            list1=list1.next;
            p=newList;
        }
        else if(list1.val>=list2.val){
                newList=list2;
                list2=list2.next;
                p=newList;
        }
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                newList.next=list1;
                list1=list1.next;
                newList=newList.next;
        }
            else if(list1.val>=list2.val){
                newList.next=list2;
                list2=list2.next;
                newList=newList.next;
            }
       }
       
        if (list1==null){
            newList.next=list2;
        }
        if(list2==null)
        {
            newList.next=list1;
        }
        return p;
        }
}

发表于 2019-05-14 21:57:00 回复(0)
递归思路:重复做一件事情,比较,然后合并,
public ListNode Merge2(ListNode list1,ListNode list2){ if (list1==null){ return list2;  } if (list2== null){ return list1;  } if (Compare(list1.val,list2.val)){
        list1.next = Merge2(list1.next,list2);  return list1;  }else {
        list2.next = Merge2(list1,list2.next);  return list2;  }
}
public boolean Compare(Comparable l1,Comparable l2){ return l1.compareTo(l2)<0; }

非递归思路:新创建一个链表,然后将分离出来的数值追加到链表尾部。注:链表采用尾插方式实现:

public ListNode Merge(ListNode list1,ListNode list2) {
    ListNode l3 = null,temp1 =null,temp2 = null,curr3 = null;  if (list1==null&&list2==null){ return null;  }else if (list1!=null&&list2==null){ return list1;  }else if (list2!=null&&list1==null){ return list2;  } while (list1!=null&& list2!=null){ if (Compare(list1.val,list2.val)){//较小的值首先插入链表  temp1 = list1.next;//将剩余部分临时存储  list1.next = null;  if (curr3==null){
                curr3 = list1;//当前值传给curr3  l3 = curr3;  }else {
                l3.next = list1;//当前值  l3 = l3.next;  }
            list1 = temp1;  }else {
            temp2 = list2.next;  list2.next = null;  if (curr3==null){
                curr3 = list2;  l3 = curr3;//将链表复制到辅助链表中  }else {
                l3.next = list2;  l3 = l3.next;  }
            list2 = temp2;  }
    } if (list1!=null){
        l3.next = list1;  } if (list2!=null){
        l3.next = list2;  } return curr3; } public boolean Compare(Comparable l1,Comparable l2){ return l1.compareTo(l2)<0; }
考虑情况多
发表于 2019-05-14 21:45:14 回复(0)
//java 17行简短非递归解答
//还顺便复习了一下短路与 和 短路或
//这是非递归的写法,可以只用一个if和else if就走完所有的情况。
//同时,因为链表节点是引用传递的,所以一开始head 指向新建的list3节点
//在后面head.next就是后面接上的第一个节点
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode list3 = new ListNode(1);
        ListNode head = list3;
        while(list1!=null||list2!=null){
            if (list1!=null && (list2==null || list1.val<=list2.val)){
                list3.next=list1;
                list1 = list1.next;
            }else if (list2!=null && (list1==null || list2.val<list1.val)){
                list3.next=list2;
                list2 = list2.next;
            }
            list3 = list3.next;
        }
        return head.next;
    }
}

发表于 2019-05-04 19:16:10 回复(0)
 public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null&&list2==null)return null;    //空判断
        if(list1==null) return list2;
        if(list2==null) return list1;
        ListNode list3=null;
        ListNode list4=null;          //新建一个节点以返回头节点
        if(list1.val>=list2.val) {           //初始化list3节点
            list3=new ListNode(list2.val);
            list4=list3;
            list2=list2.next;
        }else {                             
            list3=new ListNode(list1.val);
            list4=list3;
            list1=list1.next;
        }
        while(list1!=null|list2!=null) {        //合并两个链表
            if(list1==null) {
                list3.next=list2;
                list3=list3.next;
                list2=list2.next;
            }else if(list2==null) {
                list3.next=list1;
                list3=list3.next;
                list1=list1.next;
            }else {
                if(list1.val<=list2.val) {
                    list3.next=list1;
                    list3=list3.next;
                    list1=list1.next;
                }else {
                    list3.next=list2;
                    list3=list3.next;
                    list2=list2.next;
                }
            }
        }
        return list4;
    }
发表于 2019-05-03 11:30:35 回复(1)
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode reservedNode = null;   //保存合并后的链头
        ListNode moveNode = null;       //指向合并过程中合并后的链表的链尾
        ListNode currentNode = null;
        
        //如果两个链表为空,则返回null值
        if(list1 == null && list2 == null)
        {
            return null;
        }
        如果两个链表中一个为空,一个为非空,则返回非空一个链表的链头
        if(list1 == null && list2 != null)
        {
            return list2;
        }
        if(list1 != null && list2 == null)
        {
            return list1;
        }
        
        //查找合并后的链头
        if(list1.val < list2.val)
        {
            reservedNode = list1;
            currentNode = list1;
            list1 = list1.next;
        }
        else{
            reservedNode = list2;
            currentNode = list2;
            list2 = list2.next;
        }
        
        //将list1和list2中的值依次比较,然后添加到reservedNode后面
        //两个链表中都有未使用的结点的操作
        while(list1 != null && list2 != null)
        {
            if(list1.val < list2.val)
            {
                currentNode.next = list1;
                currentNode = currentNode.next;
                list1 = list1.next;
            }
            else{
                currentNode.next = list2;
                currentNode = currentNode.next;
                list2 = list2.next;
            }
        }
        //两个链表中其中一个链表中的结点全都被使用后的操作
        while(list1 != null)
        {
            currentNode.next = list1;
            currentNode = currentNode.next;
            list1 = list1.next;
        }
        while(list2 != null)
        {
            currentNode.next = list2;
            currentNode = currentNode.next;
            list2 = list2.next;
        }
        
        return reservedNode;    //返回合并后链表的链头
    }
}

编辑于 2019-04-22 23:06:55 回复(0)
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode list = new ListNode(0);
        ListNode temp = list;
        while(list1!=null&&list2!=null){
            // temp的后面需要接上list1,list2中较小的
            temp.next = list1.val <= list2.val ? list1 : list2;
            // temp的后面接的是list1还是list2 需要遍历下一个
            if(temp.next == list1) list1 = list1.next;
            else list2 = list2.next;
            temp = temp.next;
        }
        // list1 和 list2 中必有一个未遍历完  接到temp后面
        if(list1 == null) temp.next = list2;
        else temp.next = list1;
        return list.next;
    }
}
发表于 2019-04-20 20:42:41 回复(0)