0203._Remove_Linked_List_Elements

发表于 分类于 ， ，

203. Remove Linked List Elements

难度: Easy

刷题内容

原题连接

内容描述

删除链表中等于给定值 val 的所有节点。

示例:

1
2
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5

解题方案

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

- 空间复杂度: O(2N)

暴力解法：

  1. 将链表转化为数组
  2. 对数组进行过滤
  3. 将过滤后的数组重新转化为数组

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

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

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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  if (!head) {
    return head
  }
  let array = listNodeToArray(head)
  array = array.filter(i => (i !== val))
  return arrayToListNode(array)
};


function listNodeToArray (head) {
  let array = []
  while (head) {
    array.push(head.val)
    head = head.next
  }
  return array
}

function  arrayToListNode(array) {
  if(!array || !array.length) {
    return null
  }
  
  let node
  let head = new ListNode(array[0])
  let pnode = head  //pnode变量用来保存前一个节点
  
  for(let i = 1; i < array.length; i++) {
    node = new ListNode(array[i])
    pnode.next = node   //将前一个节点的next指向当前节点
    pnode = node   //将node赋值给pnode
  }
  
  return head
}

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

- 空间复杂度: O(1)

快慢指针：

  1. 快指针(head)每次循环都向前移动一个
  2. 慢指针(slow)只有在快指针当前节点的值不等于给定值时，才会向前移动，并在此之前将快指针当前节点指向慢指针的next

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

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

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
 * @param {number} val
 * @return {ListNode}
 */
var removeElements = function(head, val) {
  if (!head) {
    return head
  }
  let slow = new ListNode()
  let result = slow
  while (head) {
    if (head.val !== val) {
      slow.next = head
      slow = slow.next
    } else if (!head.next) {
      slow.next = null
    }
    head = head.next
  }
  return result.next
};