64 - 反转链表

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL 输出: 5->4->3->2->1->NULL

进阶: 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

解答

迭代

func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    if head.Next==nil{
        return head
    }
    var pre *ListNode
    cur := head
    for cur != null {
        temp := cur.Next
        cur.Next = pre
        pre = cur
        cur = temp
    }
    return pre
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forReverse Linked List.

Memory Usage: 2.6 MB, less than 83.33% of Go online submissions forReverse Linked List.

https://leetcode.com/problems/reverse-linked-list/discuss/210873/javascript

var reverseList = function(head) {
    let pre = null
    while(head){
        const next = head.next
        head.next = pre
        pre = head
        head = next
    }
    return pre
};

Runtime: 64 ms, faster than 30.49% of JavaScript online submissions for Reverse Linked List.

Memory Usage: 35.1 MB, less than 50.00% of JavaScript online submissions for Reverse Linked List.

有趣的是，js里面不能把pre定为ListNode，即let pre = new Listnode()的话，会报错，head最后会指向undefined。

但go里面就不会，也不能令为null。可能是gc在起作用？

递归

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    result := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return result
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forReverse Linked List.

Memory Usage: 2.9 MB, less than 33.33% of Go online submissions forReverse Linked List.

假设是这个情况：$n1 > … > n{k-1} > nk > n{k+1} < … < n_m$

目前在$nk$，所以要把$n{k+1}$的next指向$n_k$，然后把$n_k$的next指向null

var reverseList = function (head) {
  if (!head || !head.next) {
    return head
  }
  let result = reverseList(head.next)
  head.next.next = head
  head.next = null
  return result
};

Runtime: 60 ms, faster than 56.09% of JavaScript online submissions for Reverse Linked List.

Memory Usage: 34.8 MB, less than 86.96% of JavaScript online submissions for Reverse Linked List.