剑指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