# 剑指offer学习笔记：8.3 链表

### 面试题56：链表中环的入口

``````/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
// 通过快慢指针判断链表中是否存在环，如果存在环，返回相遇节点，如果不存在环，返回NULL
{
{
}
ListNode* fast = slow->next;
if (fast == NULL)
{
return NULL;
}
while(slow != NULL && fast != NULL && fast->next != NULL)
{
if (slow == fast)
{
return fast;
}
slow = slow->next;
fast = fast->next->next;
}
return NULL;
}
{
// 第一步：找到环中一个点
if (meet == NULL)
{
return NULL;
}
// 第二步：计算环的长度
int n = 1;
ListNode* tmp = meet->next;
while(tmp != meet)
{
tmp = tmp->next;
n++;
}
// 第三步：定义两个指针，指针p2先走n步
for(int i = 0; i < n; i++)
{
p2 = p2->next;
}
// p1,p2再次相遇之处，就是环的入口
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
``````

``````/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
// 通过快慢指针判断链表中是否存在环，如果存在环，返回相遇节点，如果不存在环，返回NULL
{
{
}
ListNode* fast = slow->next;
if (fast == NULL)
{
return NULL;
}
while(slow != NULL && fast != NULL && fast->next != NULL)
{
if (slow == fast)
{
return fast;
}
slow = slow->next;
fast = fast->next->next;
}
return NULL;
}
{
// 第一步：找到环中一个点
if (meet == NULL)
{
return NULL;
}
// 第二步：计算环的长度
int n = 1;
ListNode* tmp = meet->next;
while(tmp != meet)
{
tmp = tmp->next;
n++;
}
// 第三步：定义两个指针，指针p2先走n步
for(int i = 0; i < n; i++)
{
p2 = p2->next;
}
// p1,p2再次相遇之处，就是环的入口
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
``````

``````/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
{
vector list;
{
if (find(list.begin(), list.end(), pHead) == list.end())
{
}
else {
break;
}
}
}
};
``````

### 面试题57：删除链表中的重复节点

leetcode链接 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
{
return NULL;
}
{
}
ListNode* result = NULL;
ListNode* pre = NULL;
int begin = 1;
while(cur != NULL)
{
bool needDelete = false;
ListNode* next = cur->next;
// cout << next->val << endl;
// 只判断当前节点元素和下一个节点元素val是否相等，因为只有当节点值发生变化，才会走到这里，所以当前节点值和上一个节点一定不同
if (next != NULL && cur->val == next->val)
{
needDelete = true;
// cout << "here" << endl;
}
if (!needDelete)
{
pre = cur;
cur = cur->next;
if (begin == 1)
{
result = pre;
}
begin = 0;
}  else
{
// 判断当前节点需要删除，找到所有跟当前节点值相同节点，全部删除
int value = cur->val;
ListNode* tmp = cur;
while(tmp != NULL && tmp->val == value)
{
next = tmp->next;
// delete tmp;    // 不能delete头节点，会报错
// tmp = NULL;
tmp = next;
}
if (pre == NULL)
{
;
}
else{
// cout << pre->val << endl;
pre->next = tmp;
}
cur = next;
// cout << "here" << endl;
}
}
return result;
}
};
``````