本文實例講述了C++數據結構與算法之反轉鏈表的方法。分享給大家供大家參考，具體如下：
算法概述：要求實現將一條單向鏈表反轉并考慮時間復雜度。
算法分析：
數組法(略)：
將列表元素逐個保存進數組，之后再逆向重建列表
點評：實現邏輯最簡單，需要額外的內存開銷。
移動指針：
通過三個指針逐個從鏈表頭開始逐一反轉鏈表元素的指針
點評：不需要額外的內存開銷，會改變原始鏈表。
遞歸：
以遞歸的方式首先找到鏈表尾部，再逐一反轉指針
點評：不需要額外的內存開銷，不會改變原始鏈表。
算法實現：
構建鏈表結構
/* 節點結構 */struct NODE{ int data; struct NODE* next;};/* 添加元素-壓棧 */void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node;}/* 添加元素-添加 */void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; }}移動指針
/* 反轉列表 */void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反轉指針 nxt = cur->next; cur->next = pre; // 移動指針 pre = cur; cur = nxt; } *head = pre;}遞歸
/* 反轉列表-復制原表返回反轉表 */NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反轉指針 head->next->next = head; head->next = NULL; return new_head;}打印鏈表
/* 打印隊列 */void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; }}完整代碼如下：
#include <iostream>/* 節點結構 */struct NODE{ int data; struct NODE* next;};/* 添加元素-壓棧 */void push(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = *head; *head = new_node;}/* 添加元素-添加 */void add(NODE** head, int dat) { struct NODE* new_node = new NODE(); new_node->data = dat; new_node->next = NULL; if (*head != NULL) { struct NODE* temp = *head; while (temp->next != NULL) { temp = temp->next; } temp->next = new_node; } else { *head = new_node; }}/* 反轉列表 */void reverse(NODE** head) { struct NODE* pre = NULL; struct NODE* cur = *head; struct NODE* nxt; while (cur != NULL) { // 反轉指針 nxt = cur->next; cur->next = pre; // 移動指針 pre = cur; cur = nxt; } *head = pre;}/* 反轉列表-復制原表返回反轉表 */NODE* reverse(NODE* head) { if (head == NULL || head->next == NULL) { return head; } NODE* new_head = reverse(head->next); // 反轉指針 head->next->next = head; head->next = NULL; return new_head;}/* 打印隊列 */void print(NODE* head) { NODE* temp = head; while (temp != NULL) { std::cout << temp->data << std::endl; temp = temp->next; }}int main() { struct NODE* n = NULL; add(&n, 1); add(&n, 2); add(&n, 3); n = reverse(n); print(n); return 0;}希望本文所述對大家C++程序設計有所幫助。
新聞熱點
疑難解答
圖片精選
