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

本文主要是介绍剑指offer25：合并两个排序的链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

剑指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开始即有数

注意：

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

方法二：暴力解法

直接将两个链表的节点的val值放进最小优先队列priorityQueue;
然后priorityQueue依次 poll()弹出，添加至新的链表即可，注意使用了哨兵节点；
注：

不能把节点放进优先队列，因为节点ListNode没有继承Comparable，优先队列无法比较谁最小。
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而不是valcurr.next=temp;//添加节点curr=curr.next;//跟新指针}return mer.next;}
}