剑指offer25:合并两个排序的链表

导读:本篇文章讲解 剑指offer25:合并两个排序的链表,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

剑指offer25
题目要求:给两个非递减单链表l1, l2,合并为一个非递减的单链表。

方法一:迭代

类似合并两个有序数组 ,注意此题一旦有一个链表越界,则剩下的另一个直接接到curr.next即可,而不用while 多次放入! 区别数组 !

原理视频讲解

流程
1.建立一个新的链表mer , mer也是哨兵节点(不存数据),并创建curr节点作为指针,用于存储每次新加入的节点
2. 比较list1和list2,将较小的节点添加至新链表,使用curr.next来记录。
:每一轮只能添加一个节点!若一轮在list1和list2先后添加两个节点,则无法保证新链表中的递增排序!
3. 跳出循环,将剩余节点添加至新链表
4. 返回哨兵节点的next即为新链表的第一个节点

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){return list2;}
        else if(list2==null){return list1;}
        
        ListNode mer=new ListNode(-1); //创建新链表,头节点为哨兵节点,不装数据
        ListNode curr=mer;  //指针,记录新添加的节点!
        while(list1!=null&list2!=null){ //同时都不为空才比较
            if(list1.val<list2.val){
                curr.next=list1;  //将小的添加至新链表的指针后面
                list1=list1.next;
            }else{
                curr.next=list2;
                list2=list2.next;
            }
            curr=curr.next; //更新指针
        }
         //跳出循环
        if(list1==null){ //list1为null,list2都有可能
            curr.next=list2; 
        }else{
            curr.next=list1; //list1不为null,list2为null
        }
        return mer.next; //mer还是新链表的头节点,从mer.next开始即有数
            
            
            

注意:

  1. 使用哨兵节点是常见的手法,可以简化代码并防止空指针异常

方法二:暴力解法

直接将两个链表的节点的val值放进最小优先队列priorityQueue,然后依次弹出添加至新的链表即可。

  1. 不能把节点放进优先队列,因为节点ListNode没有继承Comparable,优先队列无法比较谁最小。
  2. pq弹出的是val值,类型是int,要转化为ListNode再添加至题目要求的新链表
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        PriorityQueue<Integer> pq=new PriorityQueue<>();
        //将两个链表节点的val循环放入优先队列pq 
        while(list1!=null){
            pq.add(list1.val);  // pq存的元素要继承Comparable才能被比较!
            list1=list1.next;
        }
        while(list2!=null){
            pq.add(list2.val);
            list2=list2.next;
        }
        
        ListNode mer=new ListNode(-1); //用哨兵节点mer创建新链表
        ListNode curr=mer; //curr作为记录新添加节点的指针
        while(!pq.isEmpty()){
            ListNode temp=new ListNode(pq.poll()); //每轮必须新建ListNode类来装val,链表存的是ListNode而不是val
            curr.next=temp;//添加节点
            curr=curr.next;//跟新指针
        }
        return mer.next;
    }
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/89345.html

(0)
小半的头像小半

相关推荐

极客之音——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!