0206._Reverse_Linked_List

发表于 分类于 ， ，

206. Reverse Linked List(反转链表)

难度: Easy

刷题内容

原题连接

内容描述

反转一个单链表。

示例:

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

解题方案

  • 思路1 ：暴力解法

将链表转化为数组，再利用数组重建数组。

思路
- 时间复杂度: O(N²)

- 空间复杂度: O(N)

执行用时 :96 ms, 在所有 JavaScript 提交中击败了**54.77%**的用户

内存消耗 :35.2 MB, 在所有 JavaScript 提交中击败了**30.19%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  var nodeList = []
  if (!head) {
    return head
  }
  while (head.next) {
    nodeList.push(head)
    head = head.next
  }
  nodeList.push(head)
  nodeList.forEach((node, index) => {
    if (nodeList[index - 1]) {
      node.next = nodeList[index - 1]
    } else {
      node.next = null
    }
  })
  return nodeList[nodeList.length - 1]
};

  • 思路2： 迭代法

使用parentNode缓存上次循环的结果，每次循环都生成两个新的ListNode用来翻转链表各个元素，一次迭代即可完成链表反转。

思路
- 时间复杂度: O(N)

- 空间复杂度: O(1)

执行用时 :116 ms, 在所有 JavaScript 提交中击败了**20.19%**的用户

内存消耗 :35.5 MB, 在所有 JavaScript 提交中击败了**14.78%**的用户

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
  if (!head) {
    return head
  }
  let parentNode = null
  while (head) {
    let current = new ListNode(head.val)
    current.next = parentNode
    if (head.next) {
      let next = new ListNode(head.next.val)
      next.next = current
    } else {
      let next = null
      return current
    }
    parentNode = current
    head = head.next
  }
  return head
};