溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了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++程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
