[剑指offer] 链表

链表中环的入口结点

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

解题思路：
快慢指针检测链表是否有环的原理很简单，每次 快指针走2步， 慢指针走一步， 快指针必定在环内某一节点追上慢指针。
本题还需要找出环入口，

image.png

我们假设

• 起点 到 环入口长度为X
• 环长度为 K
• 慢指针 进入环内又走了Y

当 快慢指针相遇时，
慢指针走了： X+ Y 步
快指针比慢指针多跑一个环的长度为： X+ Y+ K 步
又知 快指针 为慢指针步数的2倍
所以有 X+Y + K= 2(X+Y)
K = X+Y --> X = K-Y
我们发现慢指针正好走了环的长度 ， 并且再走 X 步 就可以走到环入口。
然而 我们并不知道X 步 有多长， 但我们发现如果让快指针重新从 起点出发，每次走一步， 那么快指针正好 走X步后 与 慢指针相遇于 环入口。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if (!pHead)
            return NULL;
        
        //快慢指针
        ListNode* low = pHead;
        ListNode* fast = pHead;
        
        //保证快指针 不出界
        while(fast->next && fast->next->next){
            // 慢走一步， 快走2步
            low = low->next;
            fast = fast->next->next;
            //快慢指针相遇
            if(low == fast)
            {
                fast = pHead;
                //快指针重新从头出发，每次一布
                // 会与 慢指针相遇 与 环入口
                while(low!= fast){
                    fast=fast->next;
                    low=low->next;
                }
                return fast;
            }  
        }
        return NULL;

    }
};

删除链表中重复的结点

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

解题思路：
这题我用了递归的写法。
deleteDuplication(node) 函数的作用 就是 返回 node 节点往后的 第一个 不重复节点（有可能不是node, 比如 node 本身就是重复节点）

设 当前节点为A， A 的下一个节点为B.
如果A 不等于 B , 那么A 一定是一个不重复的点（因为我们保证了A点和前节点不一样）， 令 A 指向 deleteDuplication（B）， 返回A点。
反之， A 等于 B， 那么A，B 都是重复点， 那么我们next(B) 直到 找到一个新的B 不等于A（这里有可能没有新B， 说明A往后 都是 同一个数， 直接返回NULL）。

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* deleteDuplication(ListNode* pHead)
    {
        //该点为空， 或者最后一个点 
       if(!pHead || (pHead && !pHead->next))
            return pHead;

        ListNode* a  = pHead;
        ListNode* b = pHead->next;
        
        if (a->val != b->val){
            a->next = deleteDuplication(b);
            return a;
        }else{
            //重复点
            while(b->val == a->val){
                if(b->next)
                    b = b->next;
                else
                    return NULL;
            }
            return deleteDuplication(b);
        }

    }
};

从尾到头打印链表

题目描述
输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。

方法一： 借助stack 先进后出， 遍历一边链表写入stack, 再把stack的元素全部 pop 到vector 中。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
#include <stack>
using namespace std;
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        vector<int> res;
        stack<int> temp;
        
        while(head){
            temp.push(head->val);
            head = head->next;
        }
        
        while(!temp.empty()){
            res.push_back(temp.top());
            temp.pop();
        }
        return res;

    }
};

方法二： 递归

先展开， 后打印。
所以程序会一直递归到最后一个节点，在把最后一个节点加入vector中， 接着回溯，一次往前加节点。

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
private:
    vector<int> res;
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        
        if(head){
            printListFromTailToHead(head->next);
            res.push_back(head->val);
        }
        return res;
    }
};