快捷導(dǎo)航

使用C++實(shí)現(xiàn)鏈表元素的反轉(zhuǎn)

更新時(shí)間：2025年02月23日 14:52:49 作者：XuanRanDev

反轉(zhuǎn)鏈表是鏈表操作中一個(gè)經(jīng)典的問(wèn)題,也是面試中常見(jiàn)的考題,本文將從思路到實(shí)現(xiàn)一步步地講解如何實(shí)現(xiàn)鏈表的反轉(zhuǎn),幫助初學(xué)者理解這一操作,我們將使用C++代碼演示具體實(shí)現(xiàn),同時(shí)分析時(shí)間復(fù)雜度和空間復(fù)雜度,需要的朋友可以參考下

問(wèn)題定義

給定一個(gè)單鏈表，我們需要將鏈表的節(jié)點(diǎn)順序反轉(zhuǎn)。例如，鏈表 1 -> 2 -> -2 -> 3 經(jīng)過(guò)反轉(zhuǎn)后變?yōu)?nbsp;3 -> -2 -> 2 -> 1。

思路分析

反轉(zhuǎn)鏈表的核心在于修改每個(gè)節(jié)點(diǎn)的 next 指針，使其指向前一個(gè)節(jié)點(diǎn)。我們可以通過(guò)遍歷鏈表，并逐個(gè)調(diào)整指針來(lái)實(shí)現(xiàn)鏈表的反轉(zhuǎn)。這個(gè)過(guò)程的基本思路如下：

先定義一個(gè)指針 cur 用于跟蹤當(dāng)前處理的節(jié)點(diǎn)，并將它初始化為 nullptr。
遍歷鏈表中的每個(gè)節(jié)點(diǎn)，將當(dāng)前節(jié)點(diǎn)的 next 指針調(diào)整為指向 cur。
更新 cur 和遍歷指針，直到遍歷完成。
返回新的鏈表頭，即原鏈表的尾節(jié)點(diǎn)。

這個(gè)過(guò)程可以在不使用額外存儲(chǔ)空間的情況下完成鏈表的反轉(zhuǎn)，因此其空間復(fù)雜度較低。

代碼實(shí)現(xiàn)

以下是使用C++實(shí)現(xiàn)鏈表反轉(zhuǎn)的代碼：

#include "bits/stdc++.h"

using namespace std;

struct Node{
    int value;
    Node* next;
};

// 反轉(zhuǎn)鏈表的函數(shù)
Node* reverseList(Node* node) {
    Node* cur = nullptr, *newNode = nullptr;
    while(node != nullptr) {
        newNode = node;            // 保存當(dāng)前節(jié)點(diǎn)
        node = node->next;         // 移動(dòng)到下一個(gè)節(jié)點(diǎn)
        newNode->next = cur;       // 將當(dāng)前節(jié)點(diǎn)的next指向前一個(gè)節(jié)點(diǎn)
        cur = newNode;             // 更新cur為當(dāng)前節(jié)點(diǎn)
    }
    return cur;                    // 返回新的頭節(jié)點(diǎn)
}

int main() {
    // 創(chuàng)建一個(gè)示例鏈表：1 -> 2 -> -2 -> 3
    Node* head = new Node{1, new Node{2, new Node{-2, new Node{3, nullptr}}}};
    
    // 打印鏈表反轉(zhuǎn)前的值
    Node* cur = head;
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
    
    // 反轉(zhuǎn)鏈表
    cur = reverseList(head);
    
    // 打印鏈表反轉(zhuǎn)后的值
    while(cur != nullptr) {
        cout << cur->value << " "; 
        cur = cur->next;
    }
    cout << endl;
}

帶頭節(jié)點(diǎn)的鏈表

若鏈表帶頭節(jié)點(diǎn)，可使用以下方式反轉(zhuǎn)鏈表，此時(shí)頭節(jié)點(diǎn)不會(huì)跟隨鏈表的反轉(zhuǎn)而變化。

Node* reverseNode(Node* head) {
	Node* curNode = nullptr, *node = head -> next;
	while(node) {
		Node* temp = node;
		node = node -> next;
		temp -> next = curNode;
		curNode = temp;
	}
	head -> next = curNode;
	return ; 
}

代碼講解

struct Node 定義了鏈表節(jié)點(diǎn)結(jié)構(gòu)體，其中 value 存儲(chǔ)節(jié)點(diǎn)值，next 存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針。
reverseList 函數(shù)用于反轉(zhuǎn)鏈表。在此函數(shù)中，我們使用兩個(gè)指針：cur 記錄已反轉(zhuǎn)部分鏈表的尾節(jié)點(diǎn)，node 遍歷鏈表并依次調(diào)整指針。
main 函數(shù)中創(chuàng)建一個(gè)簡(jiǎn)單鏈表，并分別在反轉(zhuǎn)前后打印鏈表節(jié)點(diǎn)的值。

其他實(shí)現(xiàn)方式

遞歸反轉(zhuǎn)鏈表

除了迭代法，我們還可以用遞歸的方式反轉(zhuǎn)鏈表。遞歸法的思路是從鏈表末尾開(kāi)始，將每個(gè)節(jié)點(diǎn)的 next 指針調(diào)整為其前一個(gè)節(jié)點(diǎn)，直到回到鏈表頭節(jié)點(diǎn)。這種方法的代碼實(shí)現(xiàn)如下：

時(shí)間和空間復(fù)雜度分析

對(duì)于上述代碼，反轉(zhuǎn)鏈表的時(shí)間復(fù)雜度和空間復(fù)雜度分別為：

時(shí)間復(fù)雜度：O ( n ) O(n)O(n)，其中 n nn 為鏈表節(jié)點(diǎn)數(shù)量。我們需要遍歷鏈表中的每個(gè)節(jié)點(diǎn)，因此時(shí)間復(fù)雜度為 O ( n ) O(n)O(n)。
空間復(fù)雜度：O ( 1 ) O(1)O(1)，我們只使用了幾個(gè)輔助指針來(lái)存儲(chǔ)節(jié)點(diǎn)，沒(méi)有額外占用大量空間。

總結(jié)

反轉(zhuǎn)鏈表是鏈表操作中的基礎(chǔ)知識(shí)，通過(guò)調(diào)整每個(gè)節(jié)點(diǎn)的指針可以實(shí)現(xiàn)高效的反轉(zhuǎn)操作。本文介紹了迭代法和遞歸法兩種反轉(zhuǎn)鏈表的方式，并分析了各自的優(yōu)缺點(diǎn)及復(fù)雜度，希望能對(duì)你有所幫助。

以上就是使用C++實(shí)現(xiàn)鏈表元素的反轉(zhuǎn)的詳細(xì)內(nèi)容，更多關(guān)于C++鏈表元素反轉(zhuǎn)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: