这个版本的代码已经是正确的链表反转实现。代码的逻辑如下:
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);
}