環(huán)形鏈表
給定一個(gè)鏈表揍拆，判斷鏈表中是否有環(huán)。
進(jìn)階：
你能否不使用額外空間解決此題锦亦？
思路：兩個(gè)指針舶替，一個(gè)一次前進(jìn)兩步一個(gè)，如果有一時(shí)刻兩個(gè)相交說明有環(huán)杠园。
時(shí)間復(fù)雜度：O(n)顾瞪。兩鏈表只需要循環(huán)一遍
空間復(fù)雜度：O(1)只需要保存兩個(gè)指針
class Solution {
public:
bool hasCycle(ListNode *head) {
if(head == NULL||head->next == NULL)return false;
ListNode*a,*b;
a= head;
b = a->next;
while(true){
if(b->next == NULL)return false;
b = b->next;
if(b->next == NULL)return false;
b = b->next;
a = a->next;
if(b ==a)return true;
}
return false;
}
};
環(huán)形鏈表Ⅱ
給定一個(gè)鏈表，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)抛蚁。 如果鏈表無環(huán)陈醒，則返回 null。
說明：不允許修改給定的鏈表瞧甩。
進(jìn)階：
你是否可以不用額外空間解決此題钉跷？
思路：前半部分同上題，確定有環(huán)后肚逸，兩個(gè)指針繼續(xù)一次2步/一次1步地前進(jìn)爷辙，記錄再次相遇時(shí)經(jīng)過的移動(dòng)的次數(shù)n，此時(shí)該次數(shù)n就為環(huán)的節(jié)點(diǎn)數(shù)朦促，那么將a指向頭部膝晾，將b指向a的后第n個(gè)節(jié)點(diǎn)，同時(shí)每次各走一步务冕，當(dāng)相遇時(shí)即為第一個(gè)入環(huán)點(diǎn)血当。
時(shí)間復(fù)雜度：O(n)。
空間復(fù)雜度：O(1)
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(head == NULL||head->next == NULL)return NULL;
ListNode*a,*b;
a= head;
b = a->next;
int i=0;
while(true){
if(b->next == NULL)return NULL;
b = b->next;
if(b->next == NULL)return NULL;
b = b->next;
a = a->next;
if(b ==a){
b = b->next;
b = b->next;
a = a->next;
i++;
while(a != b){
b = b->next;
b = b->next;
a = a->next;
i++;
}
break;
}
}
a = head;
b = a;
while(i>0){
b = b->next;
i--;
}
while(a != b){
a =a->next;
b = b->next;
}
return a;
}
};
相交鏈表
編寫一個(gè)程序，找到兩個(gè)單鏈表相交的起始節(jié)點(diǎn)歹颓。
例如坯屿，下面的兩個(gè)鏈表：
A: a1 → a2
↘
c1 → c2 → c3
↗
B: b1 → b2 → b3
在節(jié)點(diǎn) c1 開始相交。
注意：
如果兩個(gè)鏈表沒有交點(diǎn)巍扛，返回 null.
在返回結(jié)果后领跛，兩個(gè)鏈表仍須保持原有的結(jié)構(gòu)。
可假定整個(gè)鏈表結(jié)構(gòu)中沒有循環(huán)撤奸。
程序盡量滿足 O(n) 時(shí)間復(fù)雜度吠昭，且僅用 O(1) 內(nèi)存。
思路：題目只要求返回結(jié)果時(shí)保持原結(jié)構(gòu)胧瓜，那么耍個(gè)小聰明矢棚，運(yùn)算時(shí)將a鏈的尾部指向b的頭部，那么如果不相交就不帶環(huán)府喳，相交就變成了如上題的帶環(huán)鏈表蒲肋，交點(diǎn)就是入環(huán)點(diǎn)，所以解法如上題钝满，先檢測是否有環(huán)（是否相交）兜粘，再檢測入環(huán)點(diǎn)（相交點(diǎn)），最后返回的時(shí)候別忘了將鏈表改回來弯蚜。
時(shí)間復(fù)雜度：O(n)孔轴。
空間復(fù)雜度：O(1)
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(headA == NULL || headB == NULL)return NULL;
ListNode*a,*b,*aa;
aa = headA;
b = headB;
while(aa->next != NULL){
aa = aa->next;
}
aa->next = b;
a= headA;
b = a->next;
int i=0;
while(true){
if(b->next == NULL){
aa->next = NULL;
return NULL;
}
b = b->next;
if(b->next == NULL){
aa->next = NULL;
return NULL;
}
b = b->next;
a = a->next;
if(b ==a){
b = b->next;
b = b->next;
a = a->next;
i++;
while(a != b){
b = b->next;
b = b->next;
a = a->next;
i++;
}
break;
}
}
a = headA;
b = a;
while(i>0){
b = b->next;
i--;
}
while(a != b){
a =a->next;
b = b->next;
}
aa->next = NULL;
return a;
}
};
