題目

輸入一個鏈表的頭結點，反轉該鏈表，并返回反轉后鏈表的頭結點。

分析

假設經過若干操作，我們已經把結點 pre之前的指針調整完畢，這些結點的next指針都指向前面一個結點?，F在我們遍歷到結點cur。我們需要把調整結點的next指針讓它指向前一個結點pre。注意一旦調整了指針的指向，鏈表就斷開了，如下圖所示：

因為已經沒有指針指向結點nextNode，我們沒有辦法再遍歷到結點nextNode 了。因此為了避免鏈表斷開，我們需要在調整cur的next指針之前要把nextNode保存下來。

代碼

/*--------------------------------------------- * 日期：2015-02-11 * 作者：SJF0115 * 題目: 19.反轉鏈表 * 來源：程序員精選100題 * 博客： -----------------------------------------------*/ #include <iostream> using namespace std;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); }

代碼二

ListNode* Reverse(ListNode* head){if(head == nullptr){return nullptr;}//if// 頭結點ListNode *dunny = new ListNode(0);ListNode *p = head,*cur = nullptr;while(p){// 記住p的下一節點cur = p->next;// 頭插入法p->next = dunny->next;dunny->next = p;p = cur;}//whilereturn dunny->next;} 與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的[程序员面试题精选100题]19.反转链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。