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

給你兩個單鏈表的頭節點 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的更多內容!

推薦閱讀: