剑指offer学习笔记（8.3|剑指offer学习笔记：8.3 链表）剑指offer学习笔记：8.3链表

面试题56：链表中环的入口
【剑指offer学习笔记（8.3|剑指offer学习笔记：8.3 链表）】一个链表中含环，如何找到环的入口
牛客网链接 https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=13&&tqId=11208&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

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

解题思路：
考虑没有环的情况
思路1：双指针法。
首先需要确认环的长度，当确认环的长度n后，让指针p2先于指针p1走n步，当两个指针再次相遇，相遇点即为环的入口。
环的长度的寻找方法为，先找到环中一点，然后一边往前一边计数，当再次走到此点时，即计数为环的长度。
环中一点寻找方法为快慢指针，同面试题15。若链表存在环，快慢指针一定相遇而且相遇与环中一点。

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

思路2：如果可以用额外内存，其实把遍历过的节点存在vector里，第一个被再次遍历到的节点应该就是入口

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; */ class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { vector list; while(pHead != NULL) { if (find(list.begin(), list.end(), pHead) == list.end()) { list.push_back(pHead); pHead = pHead->next; } else { break; } } return pHead; } };

面试题57：删除链表中的重复节点
在一个被排序的链表中，如何删除重复的节点。注意不是删除重复项，而是如果节点有重复节点，则将改节点和重复节点都删除
leetcode链接 https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/

/** * Definition for singly-linked list. * struct ListNode { *int val; *ListNode *next; *ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode* deleteDuplicates(ListNode* head) { if (head == NULL) { return NULL; } if (head->next == NULL) { return head; } ListNode* result = NULL; ListNode* pre = NULL; ListNode* cur = head; 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 = https://www.it610.com/article/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; } };

解题思路：
注意！因为头节点可能被删除，因此当前删除函数应该是delete(ListNode** pHead)而不是delete(ListNode* pHead)。或者用返回值作为新的链表头。
因为链表是排序的，因此判断p->val和p->next->val即可，不需要存在vector中。