LeetCode 24.兩兩交換鏈表中的節(jié)點(diǎn)
題目：
給你一個(gè)鏈表，兩兩交換其中相鄰的節(jié)點(diǎn)，并返回交換后鏈表的頭節(jié)點(diǎn)。你必須在不修改節(jié)點(diǎn)內(nèi)部的值的情況下完成本題（即，只能進(jìn)行節(jié)點(diǎn)交換）。
方法：
本題先加入一個(gè)虛擬頭節(jié)點(diǎn)，這樣能更方便地在最后返回頭節(jié)點(diǎn)。然后按照題目要求改變指針的指向，例如原來(lái)是虛擬頭節(jié)點(diǎn)->節(jié)點(diǎn)1->節(jié)點(diǎn)2->節(jié)點(diǎn)3，通過(guò)指針操作將順序改為虛擬頭節(jié)點(diǎn)->節(jié)點(diǎn)2->節(jié)點(diǎn)1->節(jié)點(diǎn)3，這樣就能夠?qū)崿F(xiàn)節(jié)點(diǎn)的交換。
思路：
當(dāng)鏈表節(jié)點(diǎn)數(shù)為奇數(shù)時(shí)，循環(huán)終止的條件是cur->next為空，當(dāng)鏈表節(jié)點(diǎn)數(shù)為偶數(shù)時(shí)，循環(huán)終止的條件是cur->next->next為空。也可以換個(gè)角度想，因?yàn)樵诓僮髦羔樦赶虻臅r(shí)候，cur->next、cur->next->next均不能為空，為空的話，交換就無(wú)法進(jìn)行。
代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* swapPairs(ListNode* head) {
? ? ListNode* vhead=new ListNode(0);
? ? vhead->next=head;
? ? ListNode* cur=vhead;
? ? while(cur->next!=NULL&&cur->next->next!=NULL)
? ? {
? ? ? ? ListNode* temp=cur->next;
? ? ? ? ListNode* p=cur->next->next->next;
? ? ? ? cur->next=cur->next->next;
? ? ? ? cur->next->next=temp;
? ? ? ? cur->next->next->next=p;
? ? ? ? cur=cur->next->next;
? ? }
? ? return vhead->next;
? ? }
};
LeetCode 19.刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)
題目：
給你一個(gè)鏈表，刪除鏈表的倒數(shù)第?n?個(gè)結(jié)點(diǎn)，并且返回鏈表的頭結(jié)點(diǎn)。
思路:
這道題的難點(diǎn)是找到倒數(shù)第n個(gè)節(jié)點(diǎn)，這里采用雙指針的方法，定義一組指針front、last，讓front先走n+1步，然后兩個(gè)指針再同時(shí)向前移動(dòng)，直到front為空，此時(shí)last指向的是倒數(shù)n個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，再進(jìn)行刪除操作就行了。
注意：
1、這里是先走了n+1步，因?yàn)閯h除節(jié)點(diǎn)要找到前一個(gè)節(jié)點(diǎn)才行；
2、讓front先走n+1步的操作中，因?yàn)閚的數(shù)值可能會(huì)大于整個(gè)鏈表的長(zhǎng)度，所以需要要添加front！=NULL的限制條件；
3、因?yàn)橐遪+1步，如果先走了n步再在循環(huán)外走一步的話，front可能產(chǎn)生對(duì)空指針進(jìn)行操作，所以進(jìn)入循環(huán)前對(duì)n++。
代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode() : val(0), next(nullptr) {}
*? ? ListNode(int x) : val(x), next(nullptr) {}
*? ? ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
? ? ListNode* removeNthFromEnd(ListNode* head, int n) {
? ? ListNode* vhead=new ListNode(0);
? ? vhead->next=head;
? ? ListNode* front=vhead;
? ? ListNode* last=vhead;
? ? n++;
? ? while(n--&&front!=NULL)
? ? {
? ? ? ? front=front->next;
? ? }
? ? while(front!=NULL)
? ? {
? ? ? ? last=last->next;
? ? ? ? front=front->next;
? ? }
? ? ListNode* temp=last->next;
? ? last->next=last->next->next;
? ? delete temp;
? ? return vhead->next;
? ? }
};
LeetCode 面試題 02.07.鏈表相交
題目：
給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表沒(méi)有交點(diǎn)，返回?null?。
思路：
這道題考察的是鏈表相交。鏈表相交不是指節(jié)點(diǎn)的元素值相同，而是指由題目指定的節(jié)點(diǎn)開始，在某一個(gè)節(jié)點(diǎn)處兩個(gè)鏈表的指針開始相等，后續(xù)節(jié)點(diǎn)的指針也是相等的，但是這些節(jié)點(diǎn)的數(shù)值可以相等也可以不等，而這道題也就是讓我們找到題目指定的那個(gè)節(jié)點(diǎn)的位置，這一點(diǎn)可以聯(lián)系官方給的示例1來(lái)理解。
我們的目的是找到那個(gè)節(jié)點(diǎn)的位置，因?yàn)樵谙嘟恢?，兩個(gè)鏈表的后續(xù)節(jié)點(diǎn)地址都是一致的，所以相當(dāng)于把兩個(gè)鏈表的尾端對(duì)齊，然后找第一個(gè)相同的地址的節(jié)點(diǎn)位置，地址的比較通過(guò)兩個(gè)鏈表各自的指針移動(dòng)、對(duì)比進(jìn)行。假設(shè)A鏈表的長(zhǎng)度大于B鏈表，A、B鏈表尾端對(duì)齊，因?yàn)橐坏┫嘟?，A、B鏈表的地址是一致的，不存在A鏈表還繼續(xù)，B鏈表就結(jié)束的情況，所以A鏈表大于B鏈表的那一部分就可以不用比較。之后就把A鏈表的指針移到與B鏈表長(zhǎng)度相等的地方，判斷A鏈表指針是否與B鏈表指針相同，相同則返回A鏈表指針，循環(huán)結(jié)束還不同就返回NULL。
代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
? ? ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
? ? ListNode* Acur=headA;
? ? ListNode* Bcur=headB;
? ? int Alen=0;
? ? int Blen=0;
? ? while(Acur!=NULL)
? ? {
? ? ? ? Alen++;
? ? ? ? Acur=Acur->next;
? ? }
? ? while(Bcur!=NULL)
? ? {
? ? ? ? Blen++;
? ? ? ? Bcur=Bcur->next;
? ? }
? ? Acur=headA;
? ? Bcur=headB;
? ? if(Blen>Alen)
? ? {
? ? ? ? swap(Alen,Blen);
? ? ? ? swap(Acur,Bcur);
? ? }
? ? int gap=Alen-Blen;
? ? while(gap--)
? ? {
? ? ? ? Acur=Acur->next;
? ? }
? ? while(Acur!=NULL)
? ? {
? ? ? ? if(Acur==Bcur)
? ? ? ? {
? ? ? ? ? ? return Acur;
? ? ? ? }
? ? ? ? Acur=Acur->next;
? ? ? ? Bcur=Bcur->next;
? ? }
? ? return NULL;
? ? }
};
LeetCode 142.環(huán)形鏈表Ⅱ
題目：
給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開始入環(huán)的第一個(gè)節(jié)點(diǎn)。如果鏈表無(wú)環(huán)，則返回NULL。
思路：
這道題采用的是雙鏈表的解法，一個(gè)快指針fast，每次走兩個(gè)節(jié)點(diǎn)，一個(gè)慢指針，每次走一個(gè)節(jié)點(diǎn)，當(dāng)兩個(gè)指針相遇的時(shí)候，說(shuō)明鏈表里面有環(huán)。假設(shè)環(huán)的入口地址是第x個(gè)節(jié)點(diǎn)，兩個(gè)指針在環(huán)內(nèi)相遇，相遇點(diǎn)距離x節(jié)點(diǎn)為y，環(huán)的剩余距離為z，因?yàn)閮蓚€(gè)指針在相同時(shí)間內(nèi)相遇，所以有x+y=2（x+y）+y+n（z+y），其中n表示快指針在環(huán)內(nèi)轉(zhuǎn)的圈數(shù)，整理后得到x=n（z+y）-y，也即x=（n-1）（z+y）+z；也就是說(shuō)假設(shè)此時(shí)有兩個(gè)指針index1、index2。index1從head出發(fā)，index2從相遇點(diǎn)出發(fā)，它們的速度都是每次一個(gè)節(jié)點(diǎn)，那么它們一定會(huì)在環(huán)的入口地址處相遇，index1就是環(huán)的入口地址。
代碼：
/**
* Definition for singly-linked list.
* struct ListNode {
*? ? int val;
*? ? ListNode *next;
*? ? ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
? ? ListNode *detectCycle(ListNode *head) {
? ? ListNode* fast=head;
? ? ListNode* slow=head;
? ? while(fast!=NULL&&fast->next!=NULL)
? ? {
? ? ? ? fast=fast->next->next;
? ? ? ? slow=slow->next;
? ? ? ? if(fast==slow)
? ? ? ? {
? ? ? ? ? ? ListNode* p=fast;
? ? ? ? ? ? ListNode* q=head;
? ? ? ? ? ? while(p!=q)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? p=p->next;
? ? ? ? ? ? ? ? q=q->next;
? ? ? ? ? ? }
? ? ? ? return q;
? ? ? ? }
? ? }
? ? return NULL;
? ? }
};
