【剑指】3.4 代码的鲁棒性

鲁棒性要求程序对特殊的、错误的输入能作出适当的处理。防御性编程是一种好的编程习惯，在看到问题时，要多问几个“如果不……那么会怎么样”，而链表相关的问题总有大量的指针操作，往往是容易出错的。

面试题22：链表中倒数第K个节点

题目描述

输入一个链表，输出该链表中倒数第k个结点。链表尾节点是倒数第1个节点，以此类推。

解题思路

通常有下面几种解法：

1. 遍历两次链表，第一次得到链表的总长度，就可以计算出倒数第k个节点是正数第几个，第二次遍历就能找到该节点。
2. 使用栈（或递归）来保存访问过的节点，一次遍历完毕后，出栈的第k个节点就是目标节点，不过这样需要O(n)大小的额外空间。
3. 使用两个指针从头节点开始，第一个指针移动k-1次后，第二个指针才开始同步移动。当第一个指针到达末尾时，第二个指针所在节点就是目标节点。

但需要注意的是，这三种方法都需要考虑输入的情况。传入的头结点为空怎么处理，传入的k<=0怎么处理，链表长度小于k怎么处理。以第三种方法为例，若第一个指针移动完k-1次前就已经到达末尾则返回空。

public ListNode FindKthToTail(ListNode head,int k) {
    if (head==null||k<1)
        return null;
    ListNode p1=head;
    ListNode p2=p1;
    for (int step = 1; step <= k-1; step++) {
        p1=p1.next;
        if (p1==null)
            return null;
    }
    while (p1.next!= null) {
        p1=p1.next;
        p2=p2.next;
    }
    return p2;
}

面试题23：链表中环的入口节点

题目描述

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

解题思路

输入为null时自然没有环。首先判定链表中是否存在环，使用差速指针的方法。快慢指针同时出发，快指针每次移动两个节点，慢指针每次移动一个节点。如果快指针遇到了链表结尾则不存在环。两个指针每移动一次就校验他们是否相同，一旦相同则说明存在环。这时让慢指针指向头节点，两个指针同时以慢速移动，最终相遇的点就是环入口。

可简单证明，设环入口前长度为x，环长度为y，则第一次相遇时有慢指针走了x+delta(x)步，快指针走了2*(x+delta(x))步。而快指针超慢指针一圈，则他们的差值`x+delta(x)=y，说明从相遇点到环入口的距离也为x，这时从相遇点和起点同时同速度出发，相遇点就是入口了。

public ListNode EntryNodeOfLoop(ListNode pHead) {
    if(pHead==null) return null;
    /*用虚拟头节点是为了人为计数方便,一开始以为输入只有两个节点的环,
    不用虚拟头会有问题，但直接用pHead其实没问题*/
    ListNode vHead=new ListNode(0);
    vHead.next=pHead;
    ListNode fast=vHead,slow=vHead;

    while(fast.next!=null&&fast.next.next!=null){
        slow=slow.next;
        fast=fast.next.next;
        if (fast==slow){
            slow=vHead;
            while(fast!=slow){
                fast=fast.next;
                slow=slow.next;
            }
            return slow;
        }
    }
    return null;
}

面试题24：反转给定单向链表

题目描述

输入一个链表，反转链表后，输出新链表的表头。

解题思路

使用三个指针来标记当前处理的节点的前后节点，注意输入为空指针或链表只有一个节点时的情况，同时注意三个指针在初始和结束情况下的状态。

public ListNode ReverseList(ListNode head) {
    //防御型编程
    if (head==null||head.next==null)
        return head;
    ListNode pre=null,cur=head,post=cur.next;
    while (post != null) {
        //开始反转
        cur.next=pre;
        //移动三个指针
        pre=cur;
        cur=post;
        post=post.next;
    }
    //最后一次移动后post指向末尾节点的next，cur指向末尾节点，pre指向倒数第二个节点，此时还需要做一次反转
    cur.next=pre;
    return cur;
}

要注意临界情况，如开始移动和停止移动时三个指针的指向情况与它们指向节点的next指向。

面试题25：合并两个排序的链表

题目描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解题思路

首先作输入判断，并选择合适的新链表头部。接下来比较两个链表当前的头结点，将小的链接到新链表的尾部，并把该链表的头指针向后移。直到两个链表中一个（或两个）已经到达尾部，这时将剩下的链表头链接到新链表的尾部即可。

public ListNode Merge(ListNode list1,ListNode list2) {
    //防御性编程
    if (list1 == null) {
        return list2;
    }else if (list2 == null) {
        return list1;
    }

    //初始化合成后链表的头部
    ListNode head;
    if (list1.val <= list2.val) {
        head = list1;
        list1 = list1.next;
    } else {
        head=list2;
        list2=list2.next;
    }

    //依次遍历并比较list1和list2中的节点，使用pointer来连接
    ListNode pointer=head;
    while (list1 != null && list2 != null) {
        if (list1.val <= list2.val) {
            pointer.next = list1;
            pointer=pointer.next;
            list1 = list1.next;
        } else {
            pointer.next=list2;
            pointer=pointer.next;
            list2=list2.next;
        }
    }
    if (list1 != null) {
        pointer.next=list1;
    }
    if (list2 != null) {
        pointer.next=list2;
    }
    return head;
}

面试题26：树的子结构

题目描述

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

解题思路

使用方法isSubTree来递归地比较输入的两个节点是否相等且他们的孩子节点也相吻合，递归吻合的终止条件是目标节点为空，否则不吻合返回false；而方法HasSubTree中，对于刚开始输入的两棵树，递归遍历比较A的节点与B的根节点，相同时调用isSubTree方法尝试验证是否吻合，只要找到吻合就返回true，只有当遍历完A所有的节点和B比较验证都不吻合时才返回false。

public class Solution {
    public boolean HasSubtree(TreeNode root1,TreeNode root2) {
        if (root1==null||root2==null) return false;
        boolean b=false;
        if (root1.val== root2.val)
            b=isSubTree(root1,root2);
        if (b) return b;
        return HasSubtree(root1.left,root2)||HasSubtree(root1.right,root2);
    }

    private boolean isSubTree(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        } else if (root1 != null) {
            return root1.val==root2.val&&isSubTree(root1.left,root2.left)&&isSubTree(root1.right,root2.right);
        } else {
            return false;
        }
    }
}