面試題 02.07. 連結清單相交
給你兩個單連結清單的頭節點 headA 和 headB ，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單沒有交點，傳回 null 。
圖示兩個連結清單在節點 c1 開始相交：
題目資料 保證 整個鍊式結構中不存在環。
注意，函數傳回結果後，連結清單必須 保持其原始結構 。
示例 1：
輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8' 解釋：相交節點的值為 8 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [4,1,8,4,5]，連結清單 B 為 [5,0,1,8,4,5]。
在 A 中，相交節點前有 2 個節點；在 B 中，相交節點前有 3 個節點。
示例 2：
輸入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
輸出：Intersected at '2' 解釋：相交節點的值為 2 （注意，如果兩個連結清單相交則不能為 0）。
從各自的表頭開始算起，連結清單 A 為 [0,9,1,2,4]，連結清單 B 為 [3,2,4]。
在 A 中，相交節點前有 3 個節點；在 B 中，相交節點前有 1 個節點。
示例 3：
輸入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2 解釋：從各自的表頭開始算起，連結清單 A 為 [2,6,4]，連結清單 B 為 [1,5]。
由于這兩個連結清單不相交，是以 intersectVal 必須為 0，而 skipA 和 skipB 可以是任意值。
這兩個連結清單不相交，是以傳回 null 。
思路分析
題目的要求是求兩個連結清單的交點,但是這裡的交點是指指針相等,不是節點裡面的值相同.
看如下兩個連結清單，目前curA指向連結清單A的頭結點，curB指向連結清單B的頭結點,如何求得交點呢.
我們可以求出兩個連結清單的長度，并求出兩個連結清單長度的內插補點，然後讓curA移動到，和curB 末尾對齊的位置，如圖：
此時我們就可以讓CurA和CurB,從前往後周遊各自連結清單的節點,直到兩者相等,此時對應的便是交點. 如果兩個連結清單都周遊完還沒有找到,則說明沒有交點.
參考代碼
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode* curA = headA;
ListNode* curB = headB;
int lenA = 0,lenB = 0;
while(curA!=NULL){//求LenA長度
curA = curA->next;
lenA++;
}
while(curB!=NULL){//求LenB的長度
curB = curB->next;
lenB++;
}
if(lenB>lenA){//始終讓A代表的是最長的連結清單
swap(curA,curB);
swap(lenA,lenB);
}
int gap = lenA-lenB;
while(gap--){
curA = curA->next;
}
while(curA!=NULL){
if(curA==curB){//注意:連結清單有交點指的是節點重複,而不是值重複.
return curA;
}
curA = curA->next;
curB = curB->next;
}
return NULL;
} 142. 環形連結清單 II
給定一個連結清單，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。
如果連結清單中有某個節點，可以通過連續跟蹤 next 指針再次到達，則連結清單中存在環。 為了表示給定連結清單中的環，評測系統内部使用整數 pos 來表示連結清單尾連接配接到連結清單中的位置（索引從 0 開始）。如果 pos 是 -1，則在該連結清單中沒有環。注意：pos 不作為參數進行傳遞，僅僅是為了辨別連結清單的實際情況。
不允許修改 連結清單。
示例 1：
輸入：head = [3,2,0,-4], pos = 1
輸出：傳回索引為 1 解釋：連結清單中有一個環，其尾部連接配接到第二個節點。
示例 2：
輸入：head = [1,2], pos = 0
輸出：傳回索引為 0 解釋：連結清單中有一個環，其尾部連接配接到第一個節點。
示例 3：
輸入：head = [1], pos = -1 解釋：連結清單中沒有環。
思路分析
本題主要考察:
- 判斷連結清單是否環
- 如果有環，如何找到這個環的入口
如何判斷是否有環?:快慢指針
分别定義fast和slow指針,分别指向頭結點,fast每次移動兩個節點,slow每次移動一個節點,如果fast和slow指針在途中相遇,則說明這個連結清單有環.
這個過程就如同操場跑步一樣,跑的快的人在一段時間後就會追上慢的人.
如果有環，如何找到這個環的入口
從頭結點出發一個指針index1，從相遇節點 也出發一個指針index2，這兩個指針每次隻走一個節點， 那麼當這兩個指針相遇的時候就是 環形入口的節點。
證明過程可以參考卡爾大佬的文章,講的通俗易懂,嘿嘿嘿
參考代碼
ListNode *detectCycle(ListNode *head) {
ListNode* fast,*slow;
fast = head;
slow = head;
while(fast!=NULL&&fast->next!=NULL){
slow = slow->next;//slow走一步
fast = fast->next->next;//fast走兩步
if(slow==fast){//如果相遇
ListNode* index1 = fast;
ListNode* index2 = head;
while(index1!=index2){//此時如果相遇必定是入口節點
index1 = index1->next;
index2 = index2->next;
}
return index1;
}
}
return NULL;//如果沒有環,則傳回NULL
} 707. 設計連結清單
設計連結清單的實作。您可以選擇使用單連結清單或雙連結清單。單連結清單中的節點應該具有兩個屬性：val 和 next。val 是目前節點的值，next 是指向下一個節點的指針/引用。如果要使用雙向連結清單，則還需要一個屬性 prev 以訓示連結清單中的上一個節點。假設連結清單中的所有節點都是 0-index 的。
在連結清單類中實作這些功能：
- get(index)：擷取連結清單中第 index 個節點的值。如果索引無效，則傳回-1。
- addAtHead(val)：在連結清單的第一個元素之前添加一個值為 val 的節點。插入後，新節點将成為連結清單的第一個節點。
- addAtTail(val)：将值為 val 的節點追加到連結清單的最後一個元素。
- addAtIndex(index,val)：在連結清單中的第 index 個節點之前添加值為 val 的節點。如果 index 等于連結清單的長度，則該節點将附加到連結清單的末尾。如果 index 大于連結清單長度，則不會插入節點。如果index小于0，則在頭部插入節點。
- deleteAtIndex(index)：如果索引 index 有效，則删除連結清單中的第 index 個節點。
思路分析
盲猜面試出這個的可能性很大,很考查基礎.
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //連結清單變為1-> 2-> 3
linkedList.get(1); //傳回2
linkedList.deleteAtIndex(1); //現在連結清單是1-> 3
linkedList.get(1); //傳回3 參考代碼
#include<bits/stdc++.h>
using namespace std;
//很奇怪,按說是可以的...
class MyLinkedList {
public:
//定義連結清單
struct LinkedNode {
int val;
LinkedNode* next;
LinkedNode():val(0),next(NULL) {
};
LinkedNode(int x):val(x),next(NULL) {
};
LinkedNode(int x,LinkedNode* next):val(x),next(next) {
};
};
MyLinkedList() {
head = new LinkedNode();
size = 0;
}
//擷取連結清單中 index 個節點的值。如果索引無效，則傳回-1。
int get(int index) {
if(index<0 || index> size-1 ) {
return -1;
}
LinkedNode* cur = head->next;
while(index--) { //實際上是獲得index+1個節點 ,因為index是從0開始的
cur = cur->next;
}
return cur->val;
}
// 在連結清單頭部添加節點。
void addAtHead(int val) {
// ListNode *newNode = new ListNode(val,head->next);
// head->next = newNode;
head->next = new LinkedNode(val,head->next);
size++;
}
//連結清單尾部添加節點
void addAtTail(int val) {
LinkedNode* cur = head;
while(cur->next) {
cur = cur->next;
}
cur->next = new LinkedNode(val);
size++;
}
//在連結清單中的第index個節點之前添加值為val 的節點。
//如果index等于連結清單的長度，則該節點将附加到連結清單的末尾
//如果 index 大于連結清單長度，則不會插入節點。
//如果index小于0，則在頭部插入節點。
void addAtIndex(int index, int val) {
if(index>size) { //如果 index 大于連結清單長度，則不會插入節點。
return;
}
if(index<0) { //如果index小于0，則在頭部插入節點。
addAtHead(val);
}
if(index==size) { //如果index等于連結清單的長度，則該節點将附加到連結清單的末尾
addAtTail(val);
}
LinkedNode* cur = head;
while(index--) {
cur= cur->next;
}
cur->next = new LinkedNode(val,cur->next);
// ListNode *newNode = new ListNode(val);
// newNode->next = cur->next;
// cur->next = newNode;
size++;
}
//如果索引 index 有效，則删除連結清單中的第 index 個節點。
void deleteAtIndex(int index) {
if(index>=size||index<0) {
return;
}
LinkedNode* cur = head;
while(index--) {
cur = cur->next;
}
LinkedNode* temp = cur->next;
cur->next = cur->next->next;
delete temp;
size--;
}
void printLinkedList(){
LinkedNode* cur = head;
while(cur->next){
cout<<cur->next->val<<" ";
cur = cur->next;
}
cout<<endl;
}
private:
//全局變量
LinkedNode* head;
int size ;
};
int main() {
MyLinkedList* obj = new MyLinkedList();
int param_1 = obj->get(0);
cout<<param_1<<endl;
obj->addAtHead(1);
obj->printLinkedList();
obj->addAtTail(2);
obj->printLinkedList();
obj->addAtIndex(1,3);
obj->printLinkedList();
obj->deleteAtIndex(0);
obj->printLinkedList();
return 0;
}