單鏈逆置
常見的面試題，主要考查邏輯能力。

使用歸納法來解這道題。核心是下面的reverse()函數(shù)，其主要思路如下：
把一個(gè)鏈表分為三個(gè)部分：

• 前面是逆置完成（prev指針），
• 當(dāng)前指針指向的位置（curr指針），
• 后面未處理的部分（next指針）。

需要注意的地方

先想好循環(huán)體如何實(shí)現(xiàn)
snode* next = curr->next;//后面的指針
curr->next= prev;//逆置
prev = curr;//指針往后挪
curr = next;//指針往后挪

再回過頭來想curr指針和prev指針的初值
snode* prev = NULL;//想一想為什么是NULL，而不是啞結(jié)點(diǎn)header
snode* curr = header->next;//第一個(gè)真實(shí)的結(jié)點(diǎn)

最后勿忘把啞結(jié)點(diǎn)鏈接上
header->next=prev;

單向鏈表逆序reverse()函數(shù)

void reverse(snode* header) {snode* prev = NULL;snode* curr = header->next;while (curr != NULL){snode* next = curr->next;//后面的指針curr->next= prev;//逆置prev = curr;//指針往后挪curr = next;//指針往后挪}header->next = prev;//很容易忘記這一步！}

鏈表遍歷打印traverse()函數(shù)：

//遍歷鏈表traverse void traverse(snode * header) {for (snode* p = header->next; p != NULL; p = p->next)cout << p->data << " ";cout << endl; }

完整代碼：

// reverse_front_list.cpp : 此文件包含 "main" 函數(shù)。程序執(zhí)行將在此處開始并結(jié)束。#include "pch.h" #include<iostream> #include<vector>using namespace std;//結(jié)點(diǎn)結(jié)構(gòu)體 struct snode {int data;snode* next; };//遍歷鏈表traverse void traverse(snode * header) {for (snode* p = header->next; p != NULL; p = p->next)cout << p->data << " ";cout << endl; }//逆序鏈表 void reverse(snode* header) {snode* prev = NULL;//snode* curr = header->next;while (curr != NULL){snode* next = curr->next;//后面的指針curr->next= prev;//逆置prev = curr;//指針往后挪curr = next;//指針往后挪}header->next = prev;//很容易忘記這一步！}int main() {vector<snode> V = { {}, {1, NULL}, {2, NULL}, {3, NULL} };//向量鏈接成鏈表for (size_t i = 0; i+1 < V.size(); ++i){V[i].next = &V[i+ 1];}cout << "鏈表逆序之前" << endl;traverse(&V[0]);//遍歷輸出reverse(&V[0]);//逆置cout << "鏈表逆序之后" << endl;traverse(&V[0]);//遍歷輸出return 0; }

程序結(jié)果：

回答問題：
現(xiàn)在來回答為什么prev指針初值為NULL，而不是header。
第一次使用prev指針是在哪里？在循環(huán)體中。

while (curr != NULL) {snode* next = curr->next;curr->next= prev;//------------這里第一次使用prev = curr;curr = next; }

我們從具體的分析中更好地可以得出結(jié)論。
假設(shè)初始第一個(gè)結(jié)點(diǎn)數(shù)值為1，即Curr->data=1，逆置之后1就是最后一個(gè)結(jié)點(diǎn)，它應(yīng)該指向空指針，也就是curr->next=NULL.也就是這里的prev的初值應(yīng)該NULL,而不是header，因?yàn)檫@是單向鏈表。

希望對(duì)你有幫助。

《新程序員》：云原生和全面數(shù)字化實(shí)踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的单向链表的逆置问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。