如何找到自定义链表的尾部？

2015-4-14 15:18:31
收藏：0
阅读：135
评论：2

我有一个如下定义的链表：

list = nil 
list = {next=nil, value=value}

所以我试着找到链表的尾部并在其后添加一个元素：

function appendToBack(list, value)
  local list = list
  if not list then
    list = {next=nil, value=value}
  else
    local next = list.next
    while true do
      if not next then
        next = {next=nil, value=value}
        break
      else
        next = next.next
      end
    end
  end

  return list
end

使用这样的函数如何找到自定义链接列表的最后/任意节点？

点赞
用户415823
用户415823

列表将具有以下结构：

list = { -- [1]
  value = 'list head',
  next = { -- [2]
    value = 'list node',
    next = { -- [3]
      value = 'list tail',
    },
  },
}

列表的尾部是第一个 next 为 nil 的节点（即上面的节点3）。通过循环并在有有效的下一个节点时更新对尾部的引用来查找列表的尾部。一旦 tail.next 是 nil，则 tail 的值即为列表的末尾。

local tail = list
while tail.next do
  tail = tail.next
end
tail.next = { value=value }
2015-04-14 15:52:22
用户4178025
用户4178025

要找到列表中的最后一个节点，可以像这样操作：

function last (list)
  -- 仅作检查…
  if list == nil then
    return nil
  end
  -- 我们从第一个节点开始…
  local node = list
  -- …在存在下一个节点的情况下…
  while node.next ~= nil do
    -- …我们跳转到该节点。
    node = node.next
  end
  -- 当我们到达此行时，node变量保存了列表中的最后一个元素。
  return node
end

这类似于你的函数，但在这里，迭代永远不会通过列表的末尾（即node变量永远不会是nil）。如果你想，可以编写last函数的递归版本；它会更简单 :-)

现在你有了一个last函数，在你的appendToBack中，else分支应该如下：

last (list).next = { value = value }
2015-04-14 16:00:23

作者:

用户1474291

用户1474291
推荐文章