問題定義

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

思路分析

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

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

這個過程可以在不使用額外存儲空間的情況下完成鏈表的反轉(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;         // 移動到下一個節(jié)點(diǎn)
        newNode->next = cur;       // 將當(dāng)前節(jié)點(diǎn)的next指向前一個節(jié)點(diǎn)
        cur = newNode;             // 更新cur為當(dāng)前節(jié)點(diǎn)
    }
    return cur;                    // 返回新的頭節(jié)點(diǎn)
}

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é)點(diǎn)的鏈表

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

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

遞歸反轉(zhuǎn)鏈表

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

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

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

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

總結(jié)

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

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

最新評論