Java教程

有关链表的算法题中使用 辅助结点(剑指 Offer 25. 合并两个排序的链表)

本文主要是介绍有关链表的算法题中使用 辅助结点(剑指 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. 合并两个排序的链表)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!