《剑指Offer》链表考点题解

题目链接：从尾到头打印链表

题目简述：

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

题目思路

返回一个vector，可以直接调用反置函数，当然也可以遍历链表，将链表每一个指针的指向反转。

题解代码

/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode* head) {
        ListNode* now = head;
        vector<int> v;
        while(now)
        {
            v.push_back(now->val);
            now = now->next;
        }
        reverse(v.begin(), v.end());
        return v;
    }
};

题目链接：删除链表中的重复元素

题目简述：

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

题解思路

设置pre、now、next三个指针，分别指向之前、当前、和下一个，若当前和下一个元素相同，则向后遍历找出最后一个相同的，删除这些元素。

题解思路

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
    public:
        ListNode* deleteDuplication(ListNode* pHead) 
        {
            if(pHead==NULL || pHead->next==NULL) return pHead;
            else 
            {
                ListNode* newHead=new ListNode(-1);
                newHead->next=pHead;
                ListNode* pre = newHead;
                ListNode* p;
                ListNode* pnext;
                pre->next = pHead;
                p = pHead;
                
                while(p != NULL && p->next != NULL)
                {
                    pnext = p->next;
                    if(p->val == pnext->val)
                    {
                        while(pnext->val == p->val && pnext != NULL)
                            pnext = pnext->next;
                        pre->next = pnext;
                        p = pnext;
                    }
                    else
                    {
                        pre = p;
                        p = p->next;
                    }
                }
                return newHead->next;
            }
        }
};

题目链接链表中环的节点

题目描述

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

题解思路

这个一看就是快慢指针，这里不懂快慢指针的我简单介绍一下。在链表头设两个指针，快指针每次向后移动两次，慢指针移动一次，如果快慢指针最后相遇，则说明链表有环。如果想要计算环的入口，我们假定快慢指针相遇于一点，这一点到环入口点距离为A，剩下的距离为B，链表头到环入口长度为C，此时快指针路程为C+2A+B，慢指针为A+B，因为快指针速度是慢指针两倍，则有C+2A+B = 2A+2B。则B=C，C是当前慢指针绕完环一周的距离，B是新建一个慢指针从头开始走的距离，他们会在环入口相遇。

题解代码

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
        val(x), next(NULL) {
    }
};
*/
class Solution {
public:
    ListNode* EntryNodeOfLoop(ListNode* pHead)
    {
        if(pHead == NULL || pHead->next == NULL) return NULL;
        ListNode* fast = pHead;
        ListNode* slow = pHead;
        
        while(fast != NULL && fast->next != NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
            if(fast == slow)
            {
                ListNode* slow2 = pHead;
                while(slow2 != slow)
                {
                    slow2 = slow2->next;
                    slow = slow->next;
                }
                return slow2;
            }
        }
        return NULL;
    }
};