有关链表的算法题中使用 辅助结点(剑指 Offer 25. 合并两个排序的链表)
2021/12/30 14:08:31
本文主要是介绍有关链表的算法题中使用 辅助结点(剑指 Offer 25. 合并两个排序的链表),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
当做到一些操作链表的算法题时,可能需要定义一个辅助结点,目的是不直接操作题目给出的链表,但是辅助结点如何初始化就是个问题了。
比如 剑指 Offer 25. 合并两个排序的链表 中,我们需要定义一个辅助结点,我一般是这样定义的:
ListNode startNode = null; ListNode endNode = null;
但是这样定义就会有一些问题:1. 当形参的单链表为空表时,需要单独判断。 2. 在while循环的过程中,startNode是否为null需要执行不同的语句。
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode startNode = null; ListNode endNode = null; //处理特殊情况:有空链表 (这样就显得非常麻烦) if(l1==null){ if(l2==null){ return null; }else{ return l2; } } if(l2==null){ if(l1==null){ return null; }else{ return l1; } } while(l1!=null && l2!=null){ if(l1.val<=l2.val){ if(startNode==null){ //当startNode == null 时需要单独执行某些语句,降低了代码的可读性 startNode = new ListNode(l1.val); endNode = startNode; }else{ endNode.next = l1; endNode = endNode.next; } l1=l1.next; } else{ if(startNode==null){ startNode = new ListNode(l2.val); endNode = startNode; }else{ endNode.next = l2; endNode = endNode.next; } l2=l2.next; } } if(l1==null){ endNode.next=l2; }else{ endNode.next=l1; } return startNode; } }
因此最好的解决办法是:不要让 startNode指向null,而是指向一个新结点。
ListNode startNode = new ListNode(0); //引入辅助结点 ListNode endNode = startNode;
这样就不用再判断 startNode是不是为null了,减少了代码的长度,但是需要注意:这时头结点是一个数据域为0的结点,我们返回链表的时候要避开它。
return startNode.next; //返回下一个结点,避开生成的头结点
此时代码就显得简洁很多了:
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode startNode = new ListNode(0); //引入辅助结点 ListNode endNode = startNode; while(l1!=null && l2!=null){ if(l1.val<=l2.val){ endNode.next = l1; endNode = endNode.next; l1=l1.next; } else{ endNode.next = l2; endNode = endNode.next; l2=l2.next; } } if(l1==null){ //把剩余链表插入 endNode.next=l2; }else{ endNode.next=l1; } return startNode.next; } }
这篇关于有关链表的算法题中使用 辅助结点(剑指 Offer 25. 合并两个排序的链表)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南