【leetcode刷題】18.反轉鏈表—

?歡迎訂閱《leetcode》專欄，每日一題，每天進步?

有點絕望，沒刷過演算法，我發現基本的迭代都想不出來，賊打擊，而且看了答案，要自己理解記住感覺過段時間就會忘那種，害，懷疑人生

——leetcode此題熱評

前言

哈嘍，大家好，我是一條，

糊涂演算法，難得糊涂

這是一道超級經典的題目，大家要好好做哦！

Question

206. 反轉鏈表

難度：簡單

給你單鏈表的頭節點 head ，請你反轉鏈表，并回傳反轉后的鏈表，

示例 1：
輸入：head = [1,2,3,4,5]
輸出：[5,4,3,2,1]
示例 2：
輸入：head = [1,2]
輸出：[2,1]
示例 3：
輸入：head = []
輸出：[]
提示：

鏈表中節點的數目范圍是 [0, 5000]
-5000 <= Node.val <= 5000

進階：鏈表可以選用迭代或遞回方式完成反轉，你能否用兩種方法解決這道題？

Solution

這道題總體來說有兩種思路：

先實作區域替換，從而全部替換，可以用迭代或者遞回實作，
利用堆疊先進后出的特點，實作反轉

本文主要講解迭代法

在遍歷鏈表時，將當前節點的 next 指標改為指向前一個節點，
由于節點沒有參考其前一個節點，因此必須事先存盤其前一個節點，
在更改參考之前，還需要存盤后一個節點，最后回傳新的頭參考，

Code

所有leetcode代碼已同步至github

歡迎star

/**
 * @author yitiaoIT
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}