题解 | #合并两个排序的链表#

合并两个排序的链表

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337

/*
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 pre = new ListNode(-1);
        ListNode res = pre;

        //两个链表合并,首先想到是双指针
        //定义list1, list2的指针分别是 p1,p2
        ListNode p1 = list1;
        ListNode p2 = list2;

        if(list1!=null&&list2==null)
            return list1;
        else if(list1==null&&list2!=null)
            return list2;
        else if(list1==null&&list2==null)
            return null;

        //遍历list1, list2
        while(p1!=null && p2!=null){
            //当list的值小时,
            if(p1.val < p2.val){
                //将此值(这里是list1)加到pre后
                pre.next = p1;
                 //pre前移
                pre = pre.next;
                //p1前移
                p1 = p1.next;
                //当list1已经移动完毕,则需要将list2剩下的节点全部加到尾部即可
                if(p1==null){
                    pre.next = p2;
                }               
            }else if(p1.val > p2.val){
                pre.next = p2;
                pre = pre.next;
                p2 = p2.next;    
                if(p2==null){
                    pre.next = p1;
                }             
            }else{
                pre.next =p1;
                p1 = p1.next;
                pre = pre.next;
                pre.next =p2;
                p2 = p2.next;
                pre = pre.next;
            }
        }
        return res.next;
    }
}

双指针比较两个链表,依次找出小的节点,将找出的节点放到新的链表中。

如果遇到相同的值,则依次加到新的链表中。

全部评论

相关推荐

07-29 14:27
门头沟学院 Java
LMQICU:大暴雨阁下真的没绷住
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务