链表反转

输入一个链表，反转链表后，输出新链表的表头。

#include <iostream> #include <cstdlib> using namespace std; struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } }; class Solution{ public: ListNode *ReverseList(ListNode* pHead){ if(pHead == NULL||pHead->next == NULL) //如果链表为空或者只有一个节点 return pHead; ListNode *newHead,*p1,*p2; newHead = NULL; //新的头节点 p1 = pHead; //当前节点 p2 = NULL; //保存当前节点的下一个节点 while(p1!=NULL) //采用头插法插入 { p2 = p1->next; //操作节点先保存好它的下一节点信息 p1->next = newHead; //头插法操作 newHead = p1; p1 = p2; //移动到下一节点 } return newHead; } }; int main() { Solution solve; //创建链表并初始化 ListNode *s,*L,*p; L = (ListNode *)malloc(sizeof(ListNode)); L->next = NULL; for(int i = 0;i<9;i++) { s = (ListNode *)malloc(sizeof(ListNode)); s->val = i; s->next = L->next; L->next = s; } p = L->next; //第一个为头节点并没有数据 while(p!=NULL) { cout<<p->val<<" "; p = p->next; } cout<<endl; p = solve.ReverseList(L->next); //反转链表 while(p) { cout<<p->val<<" "; p = p->next; } //释放内存 p = L->next; while(p!=NULL) { free(L); L = p; p = L->next; } free(L); return 0; }

结果