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