【剑指offer】反转链表

题目描述

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

 【分析】 关于链表的题目虽然简单，但很容易出错。这道题比较不容易出错的办法是，单独定义一个新节点NewH，当找到链表的尾部时，则赋值给NewH作为新链表的头部。而遍历链表，保存下一点的状态，和之前的状态，分别需要三个节点。故一开始就定义好四个节点。代码如下：

/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL) return nullptr; ListNode* pre= nullptr;//前一个节点 ListNode* NewH = nullptr;//作为将来返回的链表头结点 ListNode* cur = pHead;//当前节点 ListNode* pNext = nullptr;//下一个节点 while(cur!= nullptr){ pNext = cur->next; if(pNext == nullptr)//当当前节点的下一个节点已经为NULL时，则找到新的链表头 NewH = cur; cur -> next = pre; pre = cur; cur = pNext; } return NewH; } };

当然，也可以这样写：

class Solution { public: ListNode* ReverseList(ListNode* pHead) { if(pHead == NULL) return nullptr; ListNode* NewH= nullptr;//始终跟随当前节点，作为新的头部 ListNode* cur = pHead;//当前节点 ListNode* pNext = nullptr;//下一个节点 while(cur!= nullptr){ pNext = cur->next; cur -> next = NewH; NewH = cur; cur = pNext; } return NewH; } };