题目描述
反转一个单链表。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
进阶:
你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
分析
反转链表的关键在于将当前节点的 next 指向前一节点。
方法一：迭代
需要两个变量，分别用来存储当前节点和上一节点，并把当前节点的 next 指向上一节点，然后前进一位，直到结束。
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
var cur = head
var prev = null
while (cur) {
var next = cur.next
cur.next = prev
prev = cur
cur = next
}
return prev
};
时间复杂度O(n)
空间复杂度O(1)
方法二：递归
递归理解起来比较绕。假设有 1->2->3->null 这样一个链表，当执行到3时开始反转，此时 list 为 3->null，head 为 2，此时2的状态为 2->3->null，要变为 3->2->null 则需要让 head.next.next = head，并且 head.next = null，画了个图：
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (head === null || head.next === null) {
return head
}
const list = reverseList(head.next)
head.next.next = head
head.next = null
return list
}
时间复杂度O(n)
空间复杂度O(n)，因为使用了递归
