[程序员面试题精选100题]19.反转链表

题目

输入一个链表的头结点，反转该链表，并返回反转后链表的头结点。

分析

假设经过若干操作，我们已经把结点 pre之前的指针调整完毕，这些结点的next指针都指向前面一个结点。现在我们遍历到结点cur。我们需要把调整结点的next指针让它指向前一个结点pre。注意一旦调整了指针的指向，链表就断开了，，如下图所示：

因为已经没有指针指向结点nextNode，我们没有办法再遍历到结点nextNode 了。因此为了避免链表断开，我们需要在调整cur的next指针之前要把nextNode保存下来。

代码

/*———————————————* 日期：2015-02-11* 作者：SJF0115* 题目: 19.反转链表* 来源：程序员精选100题* 博客：———————————————–*/;struct ListNode{int val;ListNode *next;ListNode(int x):val(x),next(NULL){}};// 输出void Show(ListNode *head){ListNode *p = head;while(p){cout<<p->val<<“->”;p = p->next;}//whilecout<<“nullptr”<<endl;}class Solution {public:void ReverseList(ListNode* &head){if(head == NULL){return;}//ifListNode *pre = NULL,*cur = head,*nextNode;while(cur){nextNode = cur->next;cur->next = pre;// 前移一个节点pre = cur;cur = nextNode;}//whilehead = pre;}//void};int main() {Solution solution;ListNode *head = new ListNode(1);ListNode *node,*p;p = head;for(int i = 2;i <= 8;++i){node = new ListNode(i);p->next = node;p = node;}//forShow(head);solution.ReverseList(head);Show(head);}

人爱美，不仅需要服饰居室之美，还需要心灵品德之美。