5/19刷题

1.验证回文字符串 Ⅱ
给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。
示例 1:
输入: "aba"
输出: True
示例 2:
输入: "abca"
输出: True
解释: 你可以删除c字符。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-palindrome-ii
思路：

class Solution {
public:
    bool checkPalindrome(const string& s, int low, int high) {//验证是不是回文串
        for(int i=low,j=high;i<j;i++,j--)
        {
            if(s[i]!=s[j])
            return false;
        }
        return true;
    }

    bool validPalindrome(string s) {
        int len=s.length();
        if(len<2) return true;
        int low=0,high=len-1;
        while(low<high)
        {
            if(s[low]==s[high])
            {
                low++;
                high--;
            }//相等则继续
            else
            {
                return checkPalindrome(s,low+1,high)||checkPalindrome(s,low,high-1);//验证[low+1,high]或[low,high-1]是不是回文串
            }
        }
        return true;
    }
};

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    //设置快慢指针，都从链表头出发，快指针每次走两步，慢指针一次走一步，假如有环，一定相遇于环中某点
    //(结论1)。接着让两个指针分别从相遇点和链表头出发，两者都改为每次走一步，最终相遇于环入口(结论2)。
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        ListNode *fast=pHead;
        ListNode *low=pHead;
        while(fast!=NULL&&fast->next!=NULL)
        {
            fast=fast->next->next;
            low=low->next;
            if(fast==low)
                break;
        }
        if(fast==NULL||fast->next==NULL) return NULL;
        low=pHead;
        while(low!=fast)//用while更好
        {
            fast=fast->next;
            low=low->next;         
        }
        return low;
    }
};

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

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
    if( pHead == nullptr ) return pHead;
    ListNode *pre = nullptr; //指向前面最晚访问过的不重复结点
    ListNode *p = pHead; //指向当前处理的结点
    ListNode *q = nullptr; //指向当前处理结点后面结点
    while( p != nullptr )
    {
        //当前结点p，（其实是p指向当前结点），与它下一个结点p->next的val相同，说明要删掉有这个val的所有结点
        if( p->next != nullptr && p->next->val == p->val )
        {
            q = p->next;
            //找到q，它指向最后一个与p val相同的结点，那p 到 q （包含） 都是要删除的
            while( q != nullptr && q->next != nullptr && q->next->val == p->val )
            {
                q = q->next;
            }
            //如果p指向链表中第一个元素，p -> ... -> q ->... , 要删除p到q, 将指向链表第一个元素的指针pHead指向q->next。
            if( p == pHead )
            {
                pHead = q->next;//注意这里是pHead不是p
            }
            else//如果p不指向链表中第一个元素，pre -> p ->...->q ->... ，要删除p到q，即pre->next = q->next
            {
                pre->next = q->next;
            }
            //当前处理的p要向链表尾部移动
            p = q->next;
        }
        else
        {
            pre = p;
            p = p->next;
        }
    }
    return pHead;                  
    }
};

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

/*
struct TreeLinkNode {
    int val;
    struct TreeLinkNode *left;
    struct TreeLinkNode *right;
    struct TreeLinkNode *next;
    TreeLinkNode(int x) :val(x), left(NULL), right(NULL), next(NULL) {

    }
};
*/
class Solution {
public:
    TreeLinkNode* GetNext(TreeLinkNode* pNode)
    {
//1.二叉树为空，则返回空；
/*2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点
        即为下一个节点；*/
/*3.节点不存在右孩子。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，
        重复之前的判断，返回结果。*/
        if(pNode==NULL) return NULL;
        if(pNode->right!=NULL)
        {
            TreeLinkNode* p=pNode->right;
            while(p->left!=NULL)
                p=p->left;
            return p;
        }
        while(pNode->next!=NULL)
        {
            TreeLinkNode *proot=pNode->next;
            if(proot->left==pNode)
                return proot;
            pNode=pNode->next;
        }
        return NULL;
    }
};