当做到一些操作链表的算法题时,可能需要定义一个辅助结点,目的是不直接操作题目给出的链表,但是辅助结点如何初始化就是个问题了。
比如 剑指 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; } }