剑指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，然后依次弹出添加至新的链表即可。
注：
- 不能把节点放进优先队列，因为节点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而不是val
curr.next=temp;//添加节点
curr=curr.next;//跟新指针
}
return mer.next;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89345.html
