C++相交鏈表和反轉鏈表詳解

Posted on by

給你兩個單鏈表的頭節點 headA 和 headB ，請你找出並返回兩個單鏈表相交的起始節點。如果兩個鏈表沒有交點，返回 null 。

在這裡插入圖片描述

思路

簡單來說，就是求兩個鏈表交點節點的 指針。 這裡同學們要註意，交點不是數值相等，而是指針相等。

為瞭方便舉例，假設節點元素數值相等，則節點指針相等。

看如下兩個鏈表，目前curA指向鏈表A的頭結點，curB指向鏈表B的頭結點：

在這裡插入圖片描述

我們求出兩個鏈表的長度，並求出兩個鏈表長度的差值，然後讓curA移動到，和curB 末尾對齊的位置，如圖：

在這裡插入圖片描述

此時我們就可以比較curA和curB是否相同，如果不相同，同時向後移動curA和curB，如果遇到curA == curB，則找到焦點。

否則循環退出返回空指針。

/**
 * 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* curA=headA;
        ListNode* curB=headB;
        int lenA=0;
        int lenB=0;
        while(curA!=nullptr){  // 求鏈表A的長度
            lenA++;
            curA=curA->next;
        }
        while(curB!=nullptr){  // 求鏈表B的長度
            lenB++;
            curB=curB->next;
        }
        //現在的curA,curB已經指向最後一個節點瞭，需要重新指向頭結點
        curA=headA;
        curB=headB; 
        if(lenA<lenB){  //假設鏈表A的長度大於鏈表B，否則交換
            swap(lenA,lenB);
            swap(curA,curB);
        }
        //gap是兩個鏈表長度的差值
        int gap=lenA-lenB; // gap=lenA-lenB 錯誤，要有返回類型
        while(gap){     // 讓curA和curB在同一起點上（末尾位置對齊）
            gap--;
            curA=curA->next;  
        }
        while(lenB){   // 遍歷curA 和 curB，遇到相同則直接返回
            if(curA==curB)
                return curA; // return curA(val) 返回節點中的值，這個寫法是錯誤的  直接return curA
            curA=curA->next;
            curB=curB->next;
            lenB--;
        } 
        return nullptr;  //沒有交點則返回空
    }
};

給你單鏈表的頭節點 head ，請你反轉鏈表，並返回反轉後的鏈表。

示例 1：

輸入：head = [1,2,3,4,5]

輸出：[5,4,3,2,1]

示例 2：

輸入：head = [1,2]

輸出：[2,1]

示例 3：

輸入：head = []

輸出：[]

雙指針思路

首先判斷鏈表是否為空，為空則返回nullptr。

接下來定義一個cur指針，指向頭結點，再定義一個pre指針，初始化為null。

然後就要開始反轉瞭，首先要把 cur->next 節點用tmp指針保存一下，也就是保存一下這個節點。

為什麼要保存一下這個節點呢，因為接下來要改變 cur->next 的指向瞭，將cur->next 指向pre ，此時已經反轉瞭第一個節點瞭。

接下來，就是循環走如下代碼邏輯瞭，繼續移動pre和cur指針。

最後，cur 指針已經指向瞭null，循環結束，鏈表也反轉完畢瞭。 此時我們return pre指針就可以瞭，pre指針就指向瞭新的頭結點。

/**
 * 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* reverseList(ListNode* head) {
        if(head==nullptr)  //對空鏈表的判斷
            return nullptr;
        ListNode* per=nullptr;
        ListNode* cur=head;
        ListNode* temp; //建立一個指針
        while(cur){  //沒必要寫 while(cur!=nullptr)，寫瞭這個還要判斷cur，會浪費時間，直接cur就可以
            temp=cur->next; //保存cur的下一個節點
            cur->next=per; //cur的下一個節點指向per,實現反轉
            per=cur;  //cur=per;錯誤，是把cur的節點賦值給per
            cur=temp; //temp=cur;錯誤，是把temp(原來的cur->next)的節點賦值給cur
        }
        return per;
    }
};

遞歸

/**
 * 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* reverse(ListNode* per,ListNode* cur){  //返回的是一個鏈表，其返回值是指針
        if(cur==nullptr)  //遞歸的終止條件
            return per;
        ListNode* temp=cur->next;
        cur->next=per;
        return reverse(cur,temp); // 調用要寫return
    }
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr) //鏈表判空
            return nullptr; 
        return reverse(NULL,head); // 調用要寫return
    }
};

總結

本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！

推薦閱讀：