題目要求

---

Reverse a singly linked list.
LeetCode 206在線測試

問題描述

---

給定一個單項鏈表，將其反轉后返回鏈表頭節點。

思路分析1

---

可以完整的遍歷一遍鏈表，將鏈表的每個節點的值存在數組中，然后反向遍歷數組重新生存一個新
鏈表。這樣做需要有O(N)的空間復雜度

代碼驗證1

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* reverseList(ListNode* head) {if (head == NULL || head->next == NULL) {return head;}vector<int> nodeVals;for (ListNode* p = head; p != NULL; p = p->next) {nodeVals.push_back(p->val);}ListNode* pNewHead = NULL;ListNode* pTail = NULL;for (int i = nodeVals.size() - 1; i >= 0; --i) {ListNode* pNew = new ListNode(nodeVals[i]);if (pTail == NULL) {pNewHead = pNew;pTail = pNew;} else {pTail->next = pNew;pTail = pNew;}}return pNewHead;} };

思路分析2

---

遍歷一次鏈表，每次遍歷到其中一個節點時，嘗試將它鏈表指向改變，改成指向他前一個節點，
原來鏈表的首節點比較特殊，需要將它的下一個指向NULL。

具體的操作流程如下圖所示：

代碼驗證2

/*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Solution { public:ListNode* reverseList(ListNode* head) {if (head == NULL || head->next == NULL) {return head;}ListNode* pre = head;pre->next = NULL;ListNode* cur = head->next;ListNode* next = NULL;while (cur != NULL) {next = cur->next;cur->next = pre;pre = cur;cur = next;}return pre; };

總結注意

---

反轉鏈表時，可以針對當前遍歷到的節點，改變當前節點的next指針指向，實現反轉當前
節點的效果。而當每個節點都執行相同的操作時，就可以實現反轉整條單項鏈表的目的

原創聲明

---

作者：hgli_00
鏈接：http://www.cnblogs.com/lihuagang/p/leetcode_206.html
來源：博客園
著作權歸作者所有，轉載請聯系作者獲得授權。

轉載于:https://www.cnblogs.com/lihuagang/p/leetcode_206.html

總結

以上是生活随笔為你收集整理的[LeetCode] [C++] 206 Reverse Linked List 反转单项链表的全部內容，希望文章能夠幫你解決所遇到的問題。

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