首页 > 试题广场 > 合并两个排序的链表
[编程题]合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

143个回答

添加回答
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)
            ListNode current1 = list1;
        ListNode current2 = list2;
        ListNode newListNode = new ListNode(100);
        ListNode head = newListNode;
        int flag = 0;
        if(list1 != null && list2 != null) {
            while (flag == 0) {
                if (current1.val < current2.val) {
                    newListNode.next = current1;
                    newListNode = newListNode.next;
                    if (current1.next != null)
                        current1 = current1.next;
                    else {
                        newListNode.next = current2;
                        flag = 1;
                    }
                } else {
                    newListNode.next = current2;
                    newListNode = newListNode.next;
                    if (current2.next != null)
                        current2 = current2.next;
                    else {
                        newListNode.next = current1;
                        flag = 1;
                    }
                }
            }
        }
        else if(list1 == null && list2 != null)
        {
            head.next = list2;
        }
        else if(list1 != null && list2 == null)
        {
            head.next = list1;
        } 
        
        return head.next;

发表于 2019-04-15 09:34:08 回复(0)
用了额外的一个链表,感觉和归并排序略像。
public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        if(list2==null){
            return list1;
        }
        ListNode list=null;
        if(list1.val<=list2.val){
             list=new ListNode(list1.val);
             list1=list1.next;
        }else{
             list=new ListNode(list2.val);
             list2=list2.next;
        }
        ListNode p=list;
        while(list1!=null&&list2!=null){
            if(list1.val<=list2.val){
                ListNode q=new ListNode(list1.val);
                list1=list1.next;
                list.next=q;
                list=list.next;
            }else{
                ListNode q=new ListNode(list2.val);
                list2=list2.next;
                list.next=q;
                list=list.next;
            }
        }
        if(list1!=null){
            list.next=list1;
        }else{
            list.next=list2;
        }
        return p;
    }

编辑于 2019-04-04 21:43:02 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode res = new ListNode(0);
        ListNode r = res;
        while(list1 != null && list2 != null){
            if(list1.val < list2.val){
                ListNode next = list1.next;
                r.next = list1;
                r = r.next;
                r.next = null;
                list1 = next;
            }
            else{
                ListNode next = list2.next;
                r.next = list2;
                r = r.next;
                r.next = null;
                list2 = next;
            }
        }
        if(list1 != null)
            r.next = list1;
        else
            r.next = list2;
        return res.next;
    }
}
//清晰的思路

发表于 2019-03-30 11:21:46 回复(0)
public ListNode Merge(ListNode list1,ListNode list2) {
            
            if (list1==null) return list2;
            if (list2==null) return list1;
            
            ListNode node = null;
            ListNode firNode=null;
            
            if(list1.val<=list2.val) {
                firNode=new ListNode(list1.val);
                node=firNode;
                list1=list1.next;
            }else {
                firNode=new ListNode(list2.val);
                node=firNode;
                list2=list2.next;
            }
            while(list1!=null||list2!=null) {
                if(list2!=null&&list1!=null&&list1.val>=list2.val) {
                    ListNode node2 = new ListNode(list2.val);
                    node.next=node2;
                    node=node2;
                    list2=list2.next;
                }else if(list2!=null&&list1!=null&&list1.val<list2.val) {
                    ListNode node2 = new ListNode(list1.val);
                    node.next=node2;
                    node=node2;
                    list1=list1.next;
                }else if(list2==null) {
                    ListNode node2 = new ListNode(list1.val);
                    node.next=node2;
                    node=node2;
                    list1=list1.next;
                }else{
                    ListNode node2 = new ListNode(list2.val);
                    node.next=node2;
                    node=node2;
                    list2=list2.next;
                }
            }
            return firNode;
        }


发表于 2019-03-27 11:26:17 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode temp = head;
        
        while(list1 != null && list2 != null) {
            if(list1.val <= list2.val) {
                temp.next = list1;
                temp = temp.next;
                list1 = list1.next;
            } else {
                temp.next = list2;
                temp = temp.next;
                list2 = list2.next;
            }
        }
        
        if(list1 != null)
            temp.next = list1;
        
        if(list2 != null)
            temp.next = list2;
        
        return head.next;
    }
}

发表于 2019-03-26 21:39:52 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode head = null;
        if(list1 ==null){
            return list2;
        }else if(list2 ==null){
            return list1;
        }
        if (list1.val < list2.val) {
            head = list1;
            list1 = list1.next;
        } else {
            head = list2;
            list2 = list2.next;
        }
        ListNode temp = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        while (list1 != null) {
            temp.next = list1;
            list1 = list1.next;
            temp = temp.next;
        }
        while (list2 != null) {
            temp.next = list2;
            list2 = list2.next;
            temp = temp.next;
        }
        return head;
    }
}
发表于 2019-03-26 16:49:37 回复(0)
 public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null&&list2==null)return null;
        if(list1==null&&list2!=null)return list2;
        if(list1!=null&&list2==null)return list1;
        ListNode head = null;
        ListNode node = null;
        ListNode p1 = list1;
        ListNode p2 = list2;
        if(p1.val<=p2.val) {
            head = p1;
            node = head;
            p1 = p1.next;
        }else {
            head = p2;
            node = head;
            p2 = p2.next;
        }
        
        while(p1!=null&&p2!=null) {
            if(p1.val<=p2.val) {
                node.next = p1;
                node = node.next;
                p1 = p1.next;
            }else {
                node.next = p2;
                node = node.next;
                p2 = p2.next;
            }
        }
        if(p1!=null) {
            node.next = p1;
        }
        if(p2!=null) {
            node.next = p2;
        }
        return head;
    }
发表于 2019-03-25 18:53:16 回复(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 list3=null;
        if(list1==null) return list2;
        if(list2==null) return list1;
        if(list1.val>=list2.val) list3=list2;
        if(list2.val>list1.val) list3=list1;
        while((list1!=null)&&(list2!=null)){
            if(list1.val>=list2.val){
               ListNode p=list2.next;
                list2.next=list1;
                list2=p;
            }else{
                ListNode q=list1.next;
                list1.next=list2;
                list1=q;
            }
        }
        return list3;
    }
}

发表于 2019-03-17 17:30:18 回复(0)

最简单的laji解法。。。

 public class Solution {
     public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        List<ListNode> list = new ArrayList();
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                list.add(list1);
                list1 = list1.next;

            } else {
                list.add(list2);
                list2 = list2.next;
            }
        }
        for (int i = 0; i < list.size() - 1; i++) {
            list.get(i).next = list.get(i + 1);

        }
        if (list1 != null) {
            list.get(list.size() - 1).next = list1;
        }
        if (list2 != null) {
            list.get(list.size() - 1).next = list2;
        }
        return list.get(0);
    }
} 


编辑于 2019-03-17 16:21:14 回复(0)
// 类似归并排序    
public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        while(list1 != null || list2 != null) {
            if ((list1 != null && list2 != null && list1.val <= list2.val) 
                    || list2 == null) {
                cur.next = list1;
                cur = cur.next;
                list1 = list1.next;
            } else {
                cur.next = list2;
                cur = cur.next;
                list2 = list2.next;
            }
        }
        cur = pre.next;
        return cur;
    }

发表于 2019-03-17 14:31:34 回复(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) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode mergeList = new ListNode(1);
        ListNode head = mergeList;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                mergeList.next = list1;
                mergeList = mergeList.next;
                list1 = list1.next;
            } else {
                mergeList.next = list2;
                mergeList = mergeList.next;
                list2 = list2.next;
            }
        }
        if (list1 != null) {
            mergeList.next = list1;
        }
        if (list2 != null) {
            mergeList.next = list2;
        }
        return head.next;
    }
}

发表于 2019-03-12 15:37:05 回复(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) {
        if(list1 == null){
            return list2;
        }

        if(list2 == null){
            return list1;
        }

        //newHead是为了表示头节点用的
        //node是为了穿针引线,将两个链表连起来
        ListNode newHead = null;
        ListNode node = null;
        while(list1 != null && list2 != null){
            //两个指针不停比较,把较小的用node串起来,并且焦较小的指针往后移动即可
            if(list1.val > list2.val){
                if(node == null){
                    newHead = list2;
                    node = list2;
                    list2 = list2.next;
                }else{
                    node.next = list2;
                    node = node.next;
                    list2 = list2.next;
                }
            }else{
                if(node == null){
                    newHead = list1;
                    node = list1;
                    list1 = list1.next;
                }else{
                    node.next = list1;
                    node = node.next;
                    list1 = list1.next;
                }
            }
        }

        //走到这里,最多只有一个链表还没遍历完,下面补全就可以了

        if(list1 != null){
            node.next = list1;
        }

        if(list2 != null){
            node.next = list2;
        }
        return newHead;
    }
}
发表于 2019-03-07 16:33:01 回复(0)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newList=new ListNode(0);//建立一个新的头结点
        ListNode result=newList;//另建一个引用指向新链表的头结点
        if(list1==null)
            return list2;
        if(list2==null)
            return list1;
        while(list1!=null&&list2!=null){
        if(list1.val<=list2.val){
            newList.next=list1;//新链表开始连接结点
            newList=list1;//此时newList已经不再指向头结点,开始后移
            list1=list1.next;
        }
            else{
                newList.next=list2;
                newList=list2;
                list2=list2.next;
            }
        }
        if(list1==null){连接剩下的链表
            newList.next=list2;
        }else{
            newList.next=list1;
        }
        return    result.next;此时头结点指向我们所需链表的最小结点,所以需要返回.next
        
    }
}

发表于 2019-03-05 18:14:57 回复(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) {
        if(list1 == null) return list2;
        if(list2 == null) return list1;
        ListNode cur;
        ListNode head;
        if(list1.val < list2.val){
            cur = head = list1;
            list1 = list1.next;
        }
        else{
            cur = head = list2;
            list2 = list2.next;
        }
        while(list1!=null&&list2!=null){
            if(list1.val < list2.val){
             cur = cur.next = list1;
             list1 = list1.next;
            }
            else{
                cur = cur.next = list2;
                list2 = list2.next;
            }
        }
        if(list1==null){
            cur.next = list2;
        }
        else{
            cur.next = list1;
        }
        return head;
    }
}

发表于 2019-02-27 10:27:38 回复(0)