24. 兩兩交換鏈表中的節(jié)點(diǎn)

解題思路：

題目的意思就是針對(duì)于一個(gè)鏈表，從頭結(jié)點(diǎn)開始挥等，每?jī)蓚€(gè)節(jié)點(diǎn)進(jìn)行交換友绝。
本題需要用到虛擬節(jié)點(diǎn)。
借助于一個(gè)while循環(huán)遍歷鏈表肝劲，循環(huán)的種植條件是當(dāng)前指針指向節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不能為空且下下一個(gè)節(jié)點(diǎn)也不能是空迁客，這是因?yàn)楫?dāng)前指針指向的節(jié)點(diǎn)是已經(jīng)交換過的節(jié)點(diǎn)，當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)和下下一個(gè)節(jié)點(diǎn)都存在辞槐，那么還能交換掷漱，循環(huán)還能繼續(xù)。
但是如果沒有下一個(gè)節(jié)點(diǎn)榄檬，也就是當(dāng)前指針的next為空指針卜范，如果沒有下下一個(gè)節(jié)點(diǎn)，那么當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)的next為空鹿榜。這兩種情況都不需要再進(jìn)行交換海雪，循環(huán)自然要停止。
交換的具體思路是舱殿，首先針對(duì)于兩個(gè)要交換的節(jié)點(diǎn)奥裸，首先用tmp指針指向待交換的前節(jié)點(diǎn)，tmp1指向后節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)沪袭，這樣就可以對(duì)后節(jié)點(diǎn)進(jìn)行操作了刺彩。
首先將待交換節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)指向后節(jié)點(diǎn)，后節(jié)點(diǎn)在指向前節(jié)點(diǎn)，前節(jié)點(diǎn)在指向下一組的前節(jié)點(diǎn)创倔。最后將當(dāng)前節(jié)點(diǎn)移動(dòng)兩位嗡害，指向下一組待交換的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next;
            ListNode* tmp1 = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = tmp;
            cur->next->next->next = tmp1;

            cur = cur->next->next;
        }
        return dummyHead->next;
    }
};

19. 刪除鏈表的倒數(shù)第 N 個(gè)結(jié)點(diǎn)

解題思路：

遇到刪除鏈表節(jié)點(diǎn)畦攘，就能使用虛擬節(jié)點(diǎn)霸妹，這樣方便操作。
題目中只給了倒數(shù)第幾個(gè)節(jié)點(diǎn)的信息知押√久可以借助于雙指針法，雙指針在本題中的作用是台盯，要?jiǎng)h除的節(jié)點(diǎn)相對(duì)尾節(jié)點(diǎn)指向的下一個(gè)空節(jié)點(diǎn)的位置罢绽，等于雙指針中前指針和后指針指向節(jié)點(diǎn)的相對(duì)位置。
首先借助于一個(gè)while循環(huán)静盅，循環(huán)的作用是指向刪除節(jié)點(diǎn)的指針向后挪動(dòng)一個(gè)位置良价，后指針就后挪一位。當(dāng)指向刪除節(jié)點(diǎn)的指針指向了空蒿叠，那么此時(shí)空節(jié)點(diǎn)的位置相對(duì)于待刪除節(jié)點(diǎn)的位置明垢，就和后指針與前指針的位置一樣了。
通過上述的相對(duì)位置市咽，就能借助于前后指針的相對(duì)位置判斷前指針是否已經(jīng)指向了待刪除節(jié)點(diǎn)痊银。但是由于刪除一個(gè)節(jié)點(diǎn)時(shí)，需要當(dāng)前指針指向待刪除的節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)施绎，所以就將后指針在往后挪移一位溯革，這樣當(dāng)后指針剛指向?yàn)榭眨爸羔槺阒赶蛄舜齽h除節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)谷醉。后續(xù)就是借助于while循環(huán)致稀，同步挪動(dòng)兩個(gè)指針，當(dāng)后指針指向?yàn)榭諘r(shí)孤紧，停止挪動(dòng)豺裆。
然后借助于一個(gè)臨時(shí)指針，對(duì)待刪除節(jié)點(diǎn)進(jìn)行刪除操作号显。
最后返回虛擬頭節(jié)點(diǎn)中next指針臭猜。

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode* fast = dummyHead;
        ListNode* slow = dummyHead;

        while(n-- && fast != NULL) {
            fast = fast->next;
        }
        fast = fast->next;
        while(fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
        ListNode* tmp = slow->next;
        slow->next = slow->next->next;
        delete tmp;
        return dummyHead->next;
    }
};

面試題 02.07. 鏈表相交

解題思路：

題目意思表達(dá)不是很明確，其實(shí)就是對(duì)于兩個(gè)鏈表押蚤，它們各有一個(gè)節(jié)點(diǎn)蔑歌，節(jié)點(diǎn)中的next指針是一樣的地址，這樣后續(xù)的節(jié)點(diǎn)就重合了揽碘，鏈表也就從下一個(gè)節(jié)點(diǎn)處開始相交次屠。
由于鏈表長(zhǎng)度不一园匹，所以需要讓兩個(gè)鏈表尾部對(duì)齊，開始遍歷的節(jié)點(diǎn)位置劫灶，也要對(duì)應(yīng)裸违。這一過程需要知道兩個(gè)鏈表的長(zhǎng)度，長(zhǎng)度通過移動(dòng)指針來確定本昏，由于不同情況下供汛，最長(zhǎng)的鏈表也不能確定，所以通過swap函數(shù)涌穆，讓最長(zhǎng)的長(zhǎng)度永遠(yuǎn)是sizea怔昨，通過sizea與sizeb做差，得到了較長(zhǎng)鏈表頭指針應(yīng)該挪動(dòng)的位數(shù)宿稀。
緊接著通過while循環(huán)趁舀，移動(dòng)兩個(gè)指針，當(dāng)存在兩個(gè)指針一致時(shí)祝沸，說明當(dāng)前指針指向的節(jié)點(diǎn)就是相交節(jié)點(diǎn)矮烹，返回該節(jié)點(diǎn)，如果直到指針指向空奋隶，整個(gè)鏈表遍歷完畢擂送，都么有找到悦荒，說明不存在交點(diǎn)唯欣。于是跳出循環(huán)，返回NULL搬味。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* cura = headA;
        ListNode* curb = headB;
        int sizea = 0;
        int sizeb = 0;
        
        while(cura != NULL) {
            sizea++;
            cura = cura->next;
        }
        while(curb != NULL) {
            sizeb++;
            curb = curb->next;
        }

        cura = headA;
        curb = headB;

        if(sizeb > sizea) {
            swap(sizea, sizeb);
            swap(cura, curb);
        }

        int gap = sizea - sizeb;

        while(gap--) {
            cura = cura->next;
        }

        while(curb != NULL) {
            if(cura == curb) {
                return cura;
            }
            cura = cura->next;
            curb = curb->next;
        }

        return NULL;
    }
};

142. 環(huán)形鏈表 II

解題思路：

這道題需要一點(diǎn)數(shù)學(xué)技巧境氢，本質(zhì)上就是一個(gè)追及問題，采用的方法為雙指針法碰纬。
如果一個(gè)鏈表中存在閉環(huán)萍聊，那么代表，不存在尾節(jié)點(diǎn)悦析，指針會(huì)一直遍歷下去寿桨，所以最外層是一個(gè)while循環(huán)，當(dāng)快指針指向最后一個(gè)節(jié)點(diǎn)或者直接指向空時(shí)强戴，停止遍歷亭螟，這說明鏈表存在尾節(jié)點(diǎn)，這時(shí)候跳出循環(huán)骑歹，返回NULL预烙。
如果存在閉環(huán)的話，由于快指針移動(dòng)速度要比慢指針移動(dòng)速度要快一步道媚，快指針會(huì)率先進(jìn)入閉環(huán)扁掸，且兩個(gè)指針一定會(huì)相遇翘县。當(dāng)兩個(gè)指針相遇的時(shí)候，借助于index1指針指向相遇節(jié)點(diǎn)谴分，index2指針指向了頭節(jié)點(diǎn)锈麸，然后移動(dòng)兩個(gè)指針，當(dāng)兩個(gè)指針相遇的時(shí)候牺蹄，指針指向的節(jié)點(diǎn)就是閉環(huán)的第一個(gè)節(jié)點(diǎn)掐隐。

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {

        ListNode* fast = head;
        ListNode* slow = head;

        while(fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast =fast->next->next;

            if(slow == fast) {
                ListNode* index1 = fast;
                ListNode* index2 = head;
                while(index1 != index2) {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index2;
            }
        }

        return NULL;
    }
};