面試題56：鏈表中環(huán)的入口
一個鏈表中含環(huán)举反，如何找到環(huán)的入口
牛客網(wǎng)鏈接 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: // 通過快慢指針判斷鏈表中是否存在環(huán)胆绊，如果存在環(huán)，返回相遇節(jié)點(diǎn)，如果不存在環(huán)赦役，返回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) { // 第一步：找到環(huán)中一個點(diǎn) ListNode* meet = meetNode(pHead); if (meet == NULL) { return NULL; } // 第二步：計算環(huán)的長度 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再次相遇之處妇汗，就是環(huán)的入口 while(p1 != p2) { p1 = p1->next; p2 = p2->next; } return p1; } };
解題思路：
考慮沒有環(huán)的情況
思路1：雙指針法。
首先需要確認(rèn)環(huán)的長度说莫，當(dāng)確認(rèn)環(huán)的長度n后杨箭，讓指針p2先于指針p1走n步，當(dāng)兩個指針再次相遇储狭，相遇點(diǎn)即為環(huán)的入口互婿。
環(huán)的長度的尋找方法為，先找到環(huán)中一點(diǎn)辽狈，然后一邊往前一邊計數(shù)擒悬，當(dāng)再次走到此點(diǎn)時，即計數(shù)為環(huán)的長度稻艰。
環(huán)中一點(diǎn)尋找方法為快慢指針懂牧，同面試題15。若鏈表存在環(huán)尊勿，快慢指針一定相遇而且相遇與環(huán)中一點(diǎn)僧凤。
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
// 通過快慢指針判斷鏈表中是否存在環(huán)，如果存在環(huán)元扔，返回相遇節(jié)點(diǎn)躯保，如果不存在環(huán)，返回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)
{
// 第一步：找到環(huán)中一個點(diǎn)
ListNode* meet = meetNode(pHead);
if (meet == NULL)
{
return NULL;
}
// 第二步：計算環(huán)的長度
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再次相遇之處途事，就是環(huán)的入口
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
};
思路2：如果可以用額外內(nèi)存，其實(shí)把遍歷過的節(jié)點(diǎn)存在vector里擅羞，第一個被再次遍歷到的節(jié)點(diǎn)應(yīng)該就是入口
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
vector<ListNode*> 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：刪除鏈表中的重復(fù)節(jié)點(diǎn)
在一個被排序的鏈表中尸变，如何刪除重復(fù)的節(jié)點(diǎn)。注意不是刪除重復(fù)項(xiàng)减俏，而是如果節(jié)點(diǎn)有重復(fù)節(jié)點(diǎn)召烂，則將改節(jié)點(diǎn)和重復(fù)節(jié)點(diǎn)都刪除
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; // 只判斷當(dāng)前節(jié)點(diǎn)元素和下一個節(jié)點(diǎn)元素val是否相等，因?yàn)橹挥挟?dāng)節(jié)點(diǎn)值發(fā)生變化娃承，才會走到這里奏夫，所以當(dāng)前節(jié)點(diǎn)值和上一個節(jié)點(diǎn)一定不同 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 { // 判斷當(dāng)前節(jié)點(diǎn)需要刪除怕篷，找到所有跟當(dāng)前節(jié)點(diǎn)值相同節(jié)點(diǎn)，全部刪除 int value = cur->val; ListNode* tmp = cur; while(tmp != NULL && tmp->val == value) { next = tmp->next; // delete tmp; // 不能delete頭節(jié)點(diǎn)酗昼，會報錯 // tmp = NULL; tmp = next; } if (pre == NULL) { ; } else{ // cout << pre->val << endl; pre->next = tmp; } cur = next; // cout << "here" << endl; } } return result; } };
解題思路：
注意廊谓！因?yàn)轭^節(jié)點(diǎn)可能被刪除，因此當(dāng)前刪除函數(shù)應(yīng)該是delete(ListNode** pHead)而不是delete(ListNode* pHead)麻削≌舯裕或者用返回值作為新的鏈表頭。
因?yàn)殒湵硎桥判虻牡牛虼伺袛鄍->val和p->next->val即可电抚，不需要存在vector中惕稻。
