这个版本的代码已经是正确的链表反转实现。代码的逻辑如下:
LinkList p = L->next;
:初始化p
为原链表的第一个节点(忽略头节点L
)。L->next = nullptr;
:将链表头的next
指针设为nullptr
,视为一个新的链表,后续将节点通过前插法插入这个“新链表”。- 在循环中:
LinkList q = p->next;
:保存当前节点p
的下一节点q
,以便后续推进。p->next = L->next;
:将当前节点p
的next
指针指向已反转部分的第一个节点,即L->next
。L->next = p;
:将头节点的next
指向当前节点p
,使p
成为已反转链表的第一个节点。p = q;
:继续处理原链表的下一个节点。
核心:前插法插入“新链表”。
void ReverseList(LinkList& L) {
LinkList p = L->next;
L->next = nullptr;
while (p) {
LinkList q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
附完整测试代码:
#include <iostream>
using namespace std;
typedef struct LNode{
int data;
LNode * next;
}Lnode,*LinkList;
void InitList(LinkList& L) {
L = new LNode;
L->next = nullptr;
}
void FreeList(LinkList& L) {
LinkList p;
while (L) {
p = L;
L = L->next;
delete p;
}
}
void AddLNode(LinkList& L) {
int num = 0;
cout << "num:";
cin >> num;
LinkList tail=L;
while (tail&&tail->next) {
tail = tail->next;
}
for (int i = 0; i < num; i++) {
LinkList newnode=new LNode;
cin >> newnode->data;
tail->next = newnode;
tail = newnode;
newnode->next = nullptr;
}
}
void ShowList(LinkList& L) {
LinkList p=L->next;
cout << "List:\t";
while (p) {
cout << p->data << " -> ";
p = p->next;
}
cout << endl;
}
void ReverseList(LinkList& L) {
LinkList p = L->next;
L->next = nullptr;
while (p) {
LinkList q = p->next;
p->next = L->next;
L->next = p;
p = q;
}
}
int main() {
LinkList L;
InitList(L);
AddLNode(L);
ShowList(L);
ReverseList(L);
ShowList(L);
AddLNode(L);
ShowList(L);
FreeList(L);
}