LeetCode206——反转链表

LeetCode206——反转链表


title: LeetCode206——反转链表
date: 2019-08-13 14:50:56
updated: 2019-08-13 14:50:56
tags:

  • 算法
  • LeetCod

题目描述

反转一个单链表。

示例:
输入: 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时开始反转,此时 list3->nullhead 为 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),因为使用了递归

发表评论

电子邮件地址不会被公开。 必填项已用*标注