C++相交鏈表和反轉(zhuǎn)鏈表詳解

更新時間：2021年08月19日 10:27:06 作者：久病成良醫(yī)

這篇文章主要介紹了C++相交鏈表和反轉(zhuǎn)鏈表,結(jié)合實例形式分析了C++相交鏈表和反轉(zhuǎn)鏈表的原理、實現(xiàn)方法及相關(guān)注意事項,需要的朋友可以參考下

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

在這里插入圖片描述

思路

簡單來說，就是求兩個鏈表交點節(jié)點的指針。這里同學(xué)們要注意，交點不是數(shù)值相等，而是指針相等。

為了方便舉例，假設(shè)節(jié)點元素數(shù)值相等，則節(jié)點指針相等。

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

在這里插入圖片描述

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

在這里插入圖片描述

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

否則循環(huán)退出返回空指針。

/**
 * 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;
        }
        //現(xiàn)在的curA,curB已經(jīng)指向最后一個節(jié)點了，需要重新指向頭結(jié)點
        curA=headA;
        curB=headB; 
        if(lenA<lenB){  //假設(shè)鏈表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) 返回節(jié)點中的值，這個寫法是錯誤的  直接return curA
            curA=curA->next;
            curB=curB->next;
            lenB--;
        } 
        return nullptr;  //沒有交點則返回空
    }
};

給你單鏈表的頭節(jié)點 head ，請你反轉(zhuǎn)鏈表，并返回反轉(zhuǎn)后的鏈表。

示例 1：

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

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

示例 2：

輸入：head = [1,2]

輸出：[2,1]

示例 3：

輸入：head = []

輸出：[]

雙指針思路

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

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

然后就要開始反轉(zhuǎn)了，首先要把 cur->next 節(jié)點用tmp指針保存一下，也就是保存一下這個節(jié)點。

為什么要保存一下這個節(jié)點呢，因為接下來要改變 cur->next 的指向了，將cur->next 指向pre ，此時已經(jīng)反轉(zhuǎn)了第一個節(jié)點了。

接下來，就是循環(huán)走如下代碼邏輯了，繼續(xù)移動pre和cur指針。

最后，cur 指針已經(jīng)指向了null，循環(huán)結(jié)束，鏈表也反轉(zhuǎn)完畢了。此時我們return pre指針就可以了，pre指針就指向了新的頭結(jié)點。

/**
 * 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的下一個節(jié)點
            cur->next=per; //cur的下一個節(jié)點指向per,實現(xiàn)反轉(zhuǎn)
            per=cur;  //cur=per;錯誤，是把cur的節(jié)點賦值給per
            cur=temp; //temp=cur;錯誤，是把temp(原來的cur->next)的節(jié)點賦值給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); // 調(diào)用要寫return
    }
    ListNode* reverseList(ListNode* head) {
        if(head==nullptr) //鏈表判空
            return nullptr; 
        return reverse(NULL,head); // 調(diào)用要寫return
    }
};