每日一题之《剑指offer》55～58题

第55题：链表中环的入口节点

难易度：⭐⭐

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

分析思路如下：
分析：
1：如何判断链表有环无环，如果有环，能否返回第一个入环节点?

image.png

对于一个成环链表，存在这样的规律：
设置一个快指针与一个慢指针，从head出发，如果快指针移动中指向了null则表明这个链表无环，如果有环，则快指针和慢指针迟早会指向同一个节点，本示例中当快指针和慢指针指向的节点重合时为如下场景：

image.png
当快指针慢指针重合时，都指向了标记为橘黄色的节点；此时，快指针回到head处，改成同慢指针一样的一次走一步。快指针和慢指针再次相遇时，指向的节点即为入环的第一个节点，如下所示：
image.png
有了这样的思路，我们就解决了一个链表是否有环，以及它的入环第一个节点是什么的问题。
代码如下：

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {

    public ListNode EntryNodeOfLoop(ListNode pHead){   
        if(pHead == null || pHead.next == null || pHead.next.next == null){
            return null;
        }
        ListNode fast = pHead.next.next;
        ListNode cur = pHead.next;
        while(fast != cur){
            if(fast.next == null || fast.next.next == null){
                return null;
            }
            fast = fast.next.next;
            cur = cur.next;
        }
        fast = pHead;
        while(fast != cur){
            fast = fast.next;
            cur = cur.next;
        }
        return cur;
    }
}

第56题：删除链表中重复的节点

难易度：⭐⭐

题目描述:
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

本题的思路为递归，因为链表是有序的链表，在递归的时候只需要考虑两种情况：
第一种情况为，当链表当前节点的下一个节点和当前节点的val值相同时
第二种情况为，链表当前节点的val值不同于下一个节点
确立好以上两点后，应用递归即可很快建立好思路。
代码如下：

/*
 public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null || pHead.next == null){
            return pHead;
        }
        if(pHead.val == pHead.next.val){
            ListNode node = pHead.next;
            while(node != null && pHead.val == node.val){
                node = node.next;
            }
            return deleteDuplication(node);
        }else{
            ListNode node = deleteDuplication(pHead.next);
            pHead.next = node;
            return pHead;
        }
    }
}

第57题：二叉树的下一个节点（后继节点）

难易度：⭐⭐

题目描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

解题思路：
如果按照中序遍历的方式去遍历整棵二叉树来寻找后继那么代价就很大，那么如何快速地找到一个节点的后继呢，思路如图：

image.png
该二叉树按照中序遍历的序列为：4 2 5 1 6 3 7
对于二叉树任意一个节点而言，都有如下结论：

1. 如果一个节点有右子树，那么这个节点的后继节点为右子树上最左的那个节点
   例如：二叉树的头节点 1 有右子树，那么后继节点为右子树上最左的那个节点即 6

2. 如果一个节点没有右子树，那么这个节点的后继节点为以此节点为左子树的最近的根节点
   例如：5这个节点没有右子树，那么这个节点的后继节点为 1；7这个节点没有右子树，那么这个节点的后继节点为null
   代码如下：

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/
public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        if(pNode == null){
            return null;
        }
        if(pNode.right != null){
            TreeLinkNode node = pNode.right;
            while(node.left != null){
                node = node.left;
            }
            return node;
        }else{
            while(pNode.next != null && pNode.next.left != pNode){
                pNode = pNode.next;
            }
            return pNode.next;
        }
    }
}

第58题：对称的二叉树

难易度：⭐⭐

题目描述:
请实现一个函数，用来判断一颗二叉树是不是对称的。
注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路分析：
本题需要从二叉树遍历的角度去思考问题，我们知道先序遍历的顺序是：cur -> cur.left -> cur.right
我们自己定义一种后序遍历，顺序为：
cur - > cur.right -> cur.left
这样，如果一个二叉树是镜像二叉树，那么先序遍历和我们自己定义的后序遍历结果是一样的，但是需要加入对null值的判断

代码如下：

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    
    boolean isSymmetrical(TreeNode pRoot){
        return isSymetrical(pRoot,pRoot);
    }
    
    boolean isSymetrical(TreeNode pRoot1,TreeNode pRoot2){
        if(pRoot1 == null && pRoot2 == null){
            return true;
        }
        if(pRoot1 == null || pRoot2 == null){
            return false;
        }
        if(pRoot1.val != pRoot2.val){
            return false;
        }
        return isSymetrical(pRoot1.left,pRoot2.right)
            && isSymetrical(pRoot1.right,pRoot2.left);
    }
}