61 - 移除链表元素

题目

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

示例:

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

解答

一个个遍历链表，如果下一个节点的值是val，那么就把next映射到它的next

var removeElements = function (head, val) {
  if (head === null) {
    return null
  }
  while (head.val === val && head != null) {
    head = head.next
    if (head === null) {
      return null
    }
  }
  let cur = head
  while (cur != null && cur.next != null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return head
};

Runtime: 72 ms, faster than 72.95% of JavaScript online submissions for Remove Linked List Elements.

Memory Usage: 37.1 MB, less than 37.50% of JavaScript online submissions for Remove Linked List Elements.

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    for head.Val == val && head != nil {
        head = head.Next
        if head == nil {
            return nil
        }
    }
    cur := head
    for cur != nil && cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return head
}

Runtime: 8 ms, faster than 87.58% of Go online submissions for Remove Linked List Elements.

Memory Usage: 4.6 MB, less than 40.00% of Go online submissions forRemove Linked List Elements.

似乎有很大优化空间。。

增加一个虚拟节点

var removeElements = function (head, val) {
  if (head === null) {
    return null
  }
  const node = new ListNode(0);
  node.next = head
  let cur = node
  while (cur.next != null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  return node.next
};

Runtime: 76 ms, faster than 50.21% of JavaScript online submissions for Remove Linked List Elements.

Memory Usage: 37.3 MB, less than 37.50% of JavaScript online submissions for Remove Linked List Elements.

怎么反而还慢了😂

https://leetcode.com/problems/remove-linked-list-elements/discuss/307269/Go-Simpliest-solution-with-dummy-list

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    node := &ListNode{0, head}
    cur := node
    for cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    return node.Next
}

Runtime: 8 ms, faster than 87.58% of Go online submissions for Remove Linked List Elements.

Memory Usage: 4.6 MB, less than 100.00% of Go online submissions for Remove Linked List Elements.

go的内存占用倒是变少了

5行这种骚操作，还是学不会哈哈😂

也可以直接拿着头节点算，最后验证下头节点

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    cur := head
    for cur.Next != nil {
        if cur.Next.Val == val {
            cur.Next = cur.Next.Next
        } else {
            cur = cur.Next
        }
    }
    if head.Val == val {
        return head.Next
    } else {
        return head
    }
}

Runtime: 4 ms, faster than 98.99% of Go online submissions for Remove Linked List Elements.

Memory Usage: 4.6 MB, less than 100.00% of Go online submissions for Remove Linked List Elements.

巨快

感觉这个思想比增加头节点更厉害。

重点是处理头节点是val的情况。

• 思路1是一开始加一个循环，留下非val作为头节点；

• 思路2是增加一个虚拟节点作为“头节点”，把头节点变成普通节点

• 思路3是直接不管头节点，最后再秋后算账

很酷吼

var removeElements = function (head, val) {
  if (head === null) {
    return null
  }
  let cur = head
  while (cur.next != null) {
    if (cur.next.val === val) {
      cur.next = cur.next.next
    } else {
      cur = cur.next
    }
  }
  if (head.val === val) {
    return head.next
  } else {
    return head
  }
};

Runtime: 76 ms, faster than 50.21% of JavaScript online submissions for Remove Linked List Elements.

Memory Usage: 37 MB, less than 50.00% of JavaScript online submissions for Remove Linked List Elements.

js只减少了一点内存的占用。

递归

var removeElements = function (head, val) {
  if (head === null) {
    return null
  }
  head.next = removeElements(head.next, val)
  if (head.val === val) {
    return head.next
  } else {
    return head
  }
};

Runtime: 72 ms, faster than 72.95% of JavaScript online submissions for Remove Linked List Elements.

Memory Usage: 37.7 MB, less than 25.00% of JavaScript online submissions for Remove Linked List Elements.

第五行是直接返回最后的一个非空节点，然后从最后一个节点判断，层层返回值。

如果是val就跳过，不是的话就留下。

感觉速度快了很多，拿空间换时间了

func removeElements(head *ListNode, val int) *ListNode {
    if head == nil {
        return nil
    }
    head.Next = removeElements(head.Next, val)
    if head.Val == val {
        return head.Next
    } else {
        return head
    }
}

Runtime: 8 ms, faster than 87.58% of Go online submissions for Remove Linked List Elements.

Memory Usage: 5.2 MB, less than 40.00% of Go online submissions forRemove Linked List Elements.