快捷導(dǎo)航

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

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

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

問題定義

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

思路分析

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

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

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

代碼實現(xiàn)

以下是使用C++實現(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;            // 保存當前節(jié)點
        node = node->next;         // 移動到下一個節(jié)點
        newNode->next = cur;       // 將當前節(jié)點的next指向前一個節(jié)點
        cur = newNode;             // 更新cur為當前節(jié)點
    }
    return cur;                    // 返回新的頭節(jié)點
}

int main() {
    // 創(chuàng)建一個示例鏈表：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é)點的鏈表

若鏈表帶頭節(jié)點，可使用以下方式反轉(zhuǎn)鏈表，此時頭節(jié)點不會跟隨鏈表的反轉(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é)點結(jié)構(gòu)體，其中 value 存儲節(jié)點值，next 存儲指向下一個節(jié)點的指針。
reverseList 函數(shù)用于反轉(zhuǎn)鏈表。在此函數(shù)中，我們使用兩個指針：cur 記錄已反轉(zhuǎn)部分鏈表的尾節(jié)點，node 遍歷鏈表并依次調(diào)整指針。
main 函數(shù)中創(chuàng)建一個簡單鏈表，并分別在反轉(zhuǎn)前后打印鏈表節(jié)點的值。

其他實現(xiàn)方式

遞歸反轉(zhuǎn)鏈表

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

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

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

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