反轉(zhuǎn)鏈表

難度：簡(jiǎn)單
來源：206. 反轉(zhuǎn)鏈表

反轉(zhuǎn)一個(gè)單鏈表。

示例:

輸入:?1->2->3->4->5->NULL
輸出:?5->4->3->2->1->NULL

進(jìn)階:

你可以迭代或遞歸地反轉(zhuǎn)鏈表。你能否用兩種方法解決這道題？

思路：

• 定義輸出鏈表 prev；

• 在遍歷鏈表時(shí)，將當(dāng)前節(jié)點(diǎn)的?next 指針改為指向前一個(gè)節(jié)點(diǎn)。由于節(jié)點(diǎn)沒有引用其前一個(gè)節(jié)點(diǎn)，因此必須事先存儲(chǔ)其前一個(gè)節(jié)點(diǎn)。在更改引用之前，還需要存儲(chǔ)后一個(gè)節(jié)點(diǎn)。最后返回新的頭引用；

• 順序遍歷鏈表 head , 將其中的元素移入鏈表 prev ；
• 圖解如下；
• 而遞歸的思路其實(shí)就是傳遞 2 個(gè)參數(shù)，prev 和 curr ，分別用來指定反轉(zhuǎn)后和前的鏈表，思路是差不多的。
  

題解一：迭代

/**
?*?Definition?for?singly-linked?list.
?*?function?ListNode(val,?next)?{
?*?????this.val?=?(val===undefined???0?:?val)
?*?????this.next?=?(next===undefined???null?:?next)
?*?}
?*/
/**
?*?@param?{ListNode}?head
?*?@return?{ListNode}
?*/
var?reverseList?=?function(head)?{
????//?方法一：迭代實(shí)現(xiàn)
????let?prev?=?null
????let?curr?=?head
????while?(curr?!=?null)?{
????????let?next?=?curr.next
????????curr.next?=?prev
????????prev?=?curr
????????curr?=?next
????}
????return?prev
};

題解二：遞歸

/**
?*?Definition?for?singly-linked?list.
?*?function?ListNode(val,?next)?{
?*?????this.val?=?(val===undefined???0?:?val)
?*?????this.next?=?(next===undefined???null?:?next)
?*?}
?*/
/**
?*?@param?{ListNode}?head
?*?@return?{ListNode}
?*/
var?reverseList?=?function(head)?{
????const?reverse?=?(prev,?curr)?=>?{
????????if?(!curr)?{
????????????return?prev
????????}
????????let?next?=?curr.next
????????curr.next?=?prev
????????return?reverse(curr,?next)
????}
????return?reverse(null,?head)
};