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

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

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

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

在這里插入圖片描述

思路

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

為了方便舉例，假設(shè)節(jié)點(diǎn)元素?cái)?shù)值相等，則節(jié)點(diǎn)指針相等。

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

在這里插入圖片描述

我們求出兩個(gè)鏈表的長(zhǎng)度，并求出兩個(gè)鏈表長(zhǎng)度的差值，然后讓curA移動(dòng)到，和curB 末尾對(duì)齊的位置，如圖：

在這里插入圖片描述

此時(shí)我們就可以比較curA和curB是否相同，如果不相同，同時(shí)向后移動(dòng)curA和curB，如果遇到curA == curB，則找到焦點(diǎn)。

否則循環(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的長(zhǎng)度
            lenA++;
            curA=curA->next;
        }
        while(curB!=nullptr){  // 求鏈表B的長(zhǎng)度
            lenB++;
            curB=curB->next;
        }
        //現(xiàn)在的curA,curB已經(jīng)指向最后一個(gè)節(jié)點(diǎn)了，需要重新指向頭結(jié)點(diǎn)
        curA=headA;
        curB=headB; 
        if(lenA<lenB){  //假設(shè)鏈表A的長(zhǎng)度大于鏈表B，否則交換
            swap(lenA,lenB);
            swap(curA,curB);
        }
        //gap是兩個(gè)鏈表長(zhǎng)度的差值
        int gap=lenA-lenB; // gap=lenA-lenB 錯(cuò)誤，要有返回類型
        while(gap){     // 讓curA和curB在同一起點(diǎn)上（末尾位置對(duì)齊）
            gap--;
            curA=curA->next;  
        }
        while(lenB){   // 遍歷curA 和 curB，遇到相同則直接返回
            if(curA==curB)
                return curA; // return curA(val) 返回節(jié)點(diǎn)中的值，這個(gè)寫法是錯(cuò)誤的  直接return curA
            curA=curA->next;
            curB=curB->next;
            lenB--;
        } 
        return nullptr;  //沒有交點(diǎn)則返回空
    }
};

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

示例 1：

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

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

示例 2：

輸入：head = [1,2]

輸出：[2,1]

示例 3：

輸入：head = []

輸出：[]

雙指針?biāo)悸?/h3>

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

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

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

為什么要保存一下這個(gè)節(jié)點(diǎn)呢，因?yàn)榻酉聛硪淖?cur->next 的指向了，將cur->next 指向pre ，此時(shí)已經(jīng)反轉(zhuǎn)了第一個(gè)節(jié)點(diǎn)了。

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

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

/**
 * 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)  //對(duì)空鏈表的判斷
            return nullptr;
        ListNode* per=nullptr;
        ListNode* cur=head;
        ListNode* temp; //建立一個(gè)指針
        while(cur){  //沒必要寫 while(cur!=nullptr)，寫了這個(gè)還要判斷cur，會(huì)浪費(fèi)時(shí)間，直接cur就可以
            temp=cur->next; //保存cur的下一個(gè)節(jié)點(diǎn)
            cur->next=per; //cur的下一個(gè)節(jié)點(diǎn)指向per,實(shí)現(xiàn)反轉(zhuǎn)
            per=cur;  //cur=per;錯(cuò)誤，是把cur的節(jié)點(diǎn)賦值給per
            cur=temp; //temp=cur;錯(cuò)誤，是把temp(原來的cur->next)的節(jié)點(diǎn)賦值給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){  //返回的是一個(gè)鏈表，其返回值是指針
        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
    }
};