链接列表删除重复项

Question

请帮忙！我觉得我很亲近！

我正在尝试使用辅助函数解决删除重复问题，该辅助函数将 return 下一个值链接到当前节点。

"use strict";

const SLinkedList = require("./linked-list.js");

function removeDups(list) {

  const visitedNumbers = {}
  let current = list.head

  let walk = (node) => {
    if (!visitedNumbers[node.value]) {
      console.log('Adding new number', node.value)
      return node
    }
    console.log('Number already exists: ', node.value)
    walk(node.next)
  }

  while (current) {
    console.log('This is current.value in while loop', current.value)
    visitedNumbers[current.value] = true
    current.next = walk(current.next)
    current = current.next
  }
  return list
}

const newList = new SLinkedList();
newList.append(1).append(2).append(1).append(3).append(3);
console.log('ORIGINAL: ', removeDups(newList).toString())

这是预期的正确输出。

ORIGINAL: { 1 } -> { 2 } -> { 3 } -> NULL

我确定问题可能来自递归“walk”函数的调用堆栈。有人知道我的问题是什么吗？

Answer 1

您遗漏了 return walk(node.next)，因此在找到重复项后，它永远不会 return 任何东西。在第 3 次递归中，找到 {3} 它将 return node，但该节点实际上永远不会 returned 到 current.next。

Answer 2

这是借助 Matriarx 的解决方案

"use strict";

const SLinkedList = require("./linked-list.js");

function removeDups(list) {

  const visitedNumbers = {}
  let current = list.head

  let walk = (node) => {
    if (node) {
      if (!visitedNumbers[node.value] || null) {
        return node
      }
      return walk(node.next)
    }
  }

  while (current) {
    visitedNumbers[current.value] = true
    current.next = walk(current.next)
    current = current.next
  }
  return list
}

我还必须添加一个 if 语句，以便它仅在 'node' 参数为真时才有效

Answer 3

这应该有效：

function removeDumps(list) {
    const memo = new Set()

    function walk(node) {
        if(node) {
            return !memo.has(node.value) ? node : walk(node.next)
        }
        return null
    }
    
    let node = list.head
    
    while(node) {
        if(!memo.has(node.value)) {
            memo.add(node.value)
        }
        
        node.next = walk(node.next)
        node = node.next
    }

    return list
}

以及没有递归的版本

function removeDumps(list) {
    const memo = new Set()
    
    let node = list.head
    let last = null
    while(node) {
        if(memo.has(node.value)) {
            node = node.next
            continue
        }
        memo.add(node.value)
        if(last) {
            last.next = node
        }
        last = node
        node = node.next
    }

    return list
}

如果不对请评论;)

链接列表删除重复项

Linked List Remove Duplicates

javascript

algorithm

recursion

linked-list

data-structures