C++培訓(xùn)之必備面試題之鏈表逆置

鏈表逆置算法是在面試中經(jīng)常會遇到的試題，下面我們來分析一二。
首先鏈表結(jié)構(gòu)如下：
typedef struct _tag_listnode
{
int data; //數(shù)據(jù)域
struct _tag_listnode *next; //下一個(gè)結(jié)點(diǎn)位置
}ListNode;
假設(shè)我們現(xiàn)在有如下鏈表：
 
我們要對這個(gè)鏈表完成逆置。
思路：

1. 用一個(gè)ListNode*指針pcur指向head->next,然后讓head->next指向NULL,此時(shí)我們把head看成是一個(gè)帶頭的空鏈表;
2. 將pcur所在鏈表的每一個(gè)結(jié)點(diǎn)，用頭插法插入到head所在的鏈表中，這樣我們就完成的鏈表的逆置.

參考代碼如下：
#include <stdio.h>
#include <stdlib.h>
 
typedef struct _tag_listnode
{
int data; //數(shù)據(jù)域
struct _tag_listnode *next; //指向下一結(jié)點(diǎn)
}ListNode;
 
//逆置鏈表函數(shù)
void list_reverse(ListNode *phead)
{
ListNode *pcur = phead->next; //將pcur指向鏈表頭結(jié)點(diǎn)的下一結(jié)點(diǎn)
phead->next = NULL; //建立一個(gè)頭為phead的空鏈表
 
//循環(huán)將pcur所在鏈表的每一個(gè)結(jié)點(diǎn)用頭插法插入到空鏈表中
while (pcur != NULL)
{
ListNode *tmp = pcur->next; //tmp指向pcur的下一個(gè)結(jié)點(diǎn)
//將pcur指向的結(jié)點(diǎn)用頭插法插入鏈表
pcur->next = phead->next;
phead->next = pcur;
 
pcur = tmp;
}
}
 
//打印鏈表內(nèi)容函數(shù)
void list_print(ListNode *phead)
{
ListNode *pcur = phead;
 
while (pcur->next != NULL)
{
printf("%d->", pcur->next->data);
pcur = pcur->next;
}
printf("NULL\n");
}
 
int main()
{
ListNode head, node1, node2, node3, node4, node5;
 
//創(chuàng)建一個(gè)鏈表如圖
node1.data = 12; node1.next = &node2;
node2.data = 21; node2.next = &node3;
node3.data = 35; node3.next = &node4;
node4.data = 46; node4.next = NULL;
head.next = &node1;
 
//打印鏈表內(nèi)容
list_print(&head);
 
//逆置鏈表
list_reverse(&head);
 
//打印鏈表內(nèi)容
list_print(&head);
 
}
經(jīng)運(yùn)行結(jié)果如下：
 
可以看到，我們的函數(shù)實(shí)現(xiàn)了對鏈表的逆置。

 本文版權(quán)歸傳智播客C++培訓(xùn)學(xué)院所有，歡迎轉(zhuǎn)載，轉(zhuǎn)載請注明作者出處。謝謝！
作者：傳智播客C/C++培訓(xùn)學(xué)院
首發(fā)：http://m.8y3kgpwe.cn/c/