代碼随想錄算法訓練營day04| 24. 兩兩交換連結清單中的節點、19.删除連結清單的倒數第N個節點 、面試題 02.07. 連結清單相交 、142.環形連結清單II

24. 兩兩交換連結清單中的節點

給你一個連結清單，兩兩交換其中相鄰的節點，并傳回交換後連結清單的頭節點。你必須在不修改節點内部的值的情況下完成本題（即，隻能進行節點交換）。題目

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;
    }
};
           

19.删除連結清單的倒數第N個節點

給你一個連結清單，删除連結清單的倒數第 n 個結點，并且傳回連結清單的頭結點。題目

雙指針法

class Solution {
public:
    int cur=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummyHead=new ListNode(0);
        dummyHead->next=head;
        ListNode* slow=dummyHead;
        ListNode* fast=dummyHead;
        while(n--&&fast!=NULL){
            fast=fast->next;
        }
        fast=fast->next;
        while(fast!=NULL){
            fast=fast->next;
            slow=slow->next;
        }
        slow->next=slow->next->next;
        return dummyHead->next;
    }
};
           

遞歸法

class Solution {
public:
    int cur=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head){
            return NULL;
        }
        head->next=removeNthFromEnd(head->next,n);
        cur++;
        if(n==cur){
            return head->next;
        }
        return head;
    }
};
           

面試題 02.07. 連結清單相交

給你兩個單連結清單的頭節點 headA 和 headB ，請你找出并傳回兩個單連結清單相交的起始節點。如果兩個連結清單沒有交點，傳回 null 。題目

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA=headA;
        ListNode* curB=headB;
        int lenA=0;
        int lenB=0;
        //得到連結清單A的長度
        while(curA!=NULL){
            lenA++;
            curA=curA->next;
        }
        //得到連結清單B的長度
        while(curB!=NULL){
            lenB++;
            curB=curB->next;
        }
        //讓curA,curB再次對準連結清單頭
        curA=headA;
        curB=headB;
        //lenA始終表示為較長連結清單的長度，curA始終指向較長連結清單的表頭
        if(lenB>lenA){
            swap(lenA,lenB);
            swap(curA,curB);
        }
        int gap = lenA-lenB;
        //讓curA,curB在同一起點上
        while(gap--){
            curA = curA->next;
        }
        //周遊curA 和 curB，遇到相同則直接傳回
        while(curA!=NULL){
            if(curA==curB){
                return curA;
            }
            curA=curA->next;
            curB=curB->next;
        }
        return NULL;
    }
};
           

142.環形連結清單II

給定一個連結清單的頭節點 head ，傳回連結清單開始入環的第一個節點。 如果連結清單無環，則傳回 null。題目

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;
    }
};