1、LeetCode24 兩兩交換鏈表中的節(jié)點(diǎn)

題目鏈接：24、兩兩交換鏈表中的節(jié)點(diǎn)

要想清楚終止條件，cur每次指向要交換的兩個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)，cur = cur->next->next;

若鏈表元素個(gè)數(shù)為偶數(shù) , 則最后時(shí)刻 cur->next = NULL；

若鏈表元素個(gè)數(shù)為奇數(shù)，則最后時(shí)刻 cur->next->next = NULL;

最后要返回 dummyHead->next, 因?yàn)榻粨Q節(jié)點(diǎn)后 head 為 “2”，不是原來的 “1”。

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode * dummyHead = new ListNode(0);
        dummyHead->next = head;
        ListNode * cur = dummyHead;

        while(cur->next!=NULL && cur->next->next!=NULL)
        {
            ListNode * temp = cur->next;
            ListNode * temp1 = cur->next->next->next;

            cur->next = cur->next->next;
            cur->next->next = temp;
            cur->next->next->next = temp1;

            cur = cur->next->next;
        }

        return dummyHead->next;
    }
};

2、LeetCode19 刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

題目鏈接：19、刪除鏈表的倒數(shù)第N個(gè)節(jié)點(diǎn)

用快慢指針，快指針先向后移動(dòng)N+1個(gè)節(jié)點(diǎn)，然后當(dāng)快指針不為NULL時(shí)，快慢指針一起向后移動(dòng)，快指針為NULL時(shí)，慢指針剛好移動(dòng)到 倒數(shù)第N個(gè)節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)。

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

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

        ListNode * temp = slow->next;
        slow->next = slow->next->next;
        delete temp;

        return dummyHead->next;
    }
};

3、LeetCode160 鏈表相交

題目鏈接：160 鏈表相交

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * cura = headA;
        ListNode * curb = headB;
        int lenA = 0;
        int lenB = 0;

        while(cura)
        {
            lenA++;
            cura = cura->next;
        }
        while(curb)
        {
            lenB++;
            curb = curb->next;
        }
        cura = headA;
        curb = headB;
        
        // 讓curA為最長鏈表的頭，lenA為其長度
        if (lenB > lenA)
        {
            swap(lenA,lenB);
            swap(cura,curb);
        }

        //求長度差
        int gap = lenA - lenB;
        while (gap--)
        {
            cura = cura->next;
        }

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

4、LeetCode142 環(huán)形鏈表

題目鏈接：142、環(huán)形鏈表

找相遇節(jié)點(diǎn)，相遇節(jié)點(diǎn)和頭結(jié)點(diǎn)同時(shí)出發(fā)，相遇時(shí)即為環(huán)形入口節(jié)點(diǎn)。（太厲害了，自己是想不出來。）

文章來源地址http://www.zghlxwxcb.cn/news/detail-454670.html

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 = head;
                ListNode * index2 = fast;
                while (index1 != index2)
                {
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};

到了這里，關(guān)于代碼隨想錄刷題第4天|LeetCode24、LeetCode19、LeetCode160、LeetCode142的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！