提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

合并两个排序的链表_16

排序
2023-04-18 16:10:23 时间

上代码：

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

        ListNode head=null;
        ListNode curr=null;
        while (list1!=null||list2!=null){
            if (list1==null){
                while (list2!=null){
                    curr.next=list2;
                    curr=list2;
                    list2=list2.next;
                }
                return head;
            }
            if (list2==null){
                while (list1!=null){
                    curr.next=list1;
                    curr=list1;
                    list1=list1.next;
                }
                return head;
            }
            //1 2 8 9 10
            //2 5 5 7 8
            if (list1.val<= list2.val){
                if (head==null){
                    head=list1;
                    curr=head;
                }else {
                    curr.next=list1;
                    curr=list1;
                }
                list1=list1.next;
            }else {
                if (head==null){
                    head=list2;
                    curr=head;
                }else {
                    curr.next=list2;
                    curr=list2;
                }
                list2=list2.next;
            }
        }
        return head;
    }

这是第一版本的；思路，如果遍历过程中有一个集合为空了，那么就把另外一个链表里的结点都添加到新链表里，实际上我们这个时候可以直接把另外一个不为空的链表直接加在我们新链表后面了

上代码：

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

        ListNode head=null;
        ListNode curr=null;
        while (list1!=null&&list2!=null){
            if (list1.val<= list2.val){
                if (head==null){
                    head=list1;
                    curr=head;
                }else {
                    curr.next=list1;
                    curr=list1;
                }
                list1=list1.next;
            }else {
                if (head==null){
                    head=list2;
                    curr=head;
                }else {
                    curr.next=list2;
                    curr=list2;
                }
                list2=list2.next;
            }
        }
        if (list1==null){
            curr.next=list2;
        }else {
            curr.next=list1;
        }
        return head;
    }

相关文章