用 JavaScript 实现链表操作 - 10 Move Node In-place

CNZPH 发布于2019-08-20 13:37 / 1991人阅读

摘要：需求实现一个函数，把源链表的头结点移到目标链表的开头。要求是不能修改两个链表的引用。跟前一个不同的是，这个是在不改变引用的情况下修改两个链表自身。最优的方案这个算法考的是对链表节点的插入和删除。大致思路为对做删除一个节点的操作。

TL;DR

用 in-place 的方式把一个链表的首节点移到另一个链表（不改变链表的引用），系列目录见前言和目录。

需求

实现一个 moveNode() 函数，把源链表的头结点移到目标链表的开头。要求是不能修改两个链表的引用。

var source = 1 -> 2 -> 3 -> null
var dest = 4 -> 5 -> 6 -> null
moveNode(source, dest)
source === 2 -> 3 -> null
dest === 1 -> 4 -> 5 -> 6 -> null

当碰到以下的情况应该抛出异常：

源链表为 null

目标链表为 null

源链表是空节点，data 属性为 null 的节点定义为空节点。

跟前一个 kata 不同的是，这个 kata 是在不改变引用的情况下修改两个链表自身。因此 moveNode() 函数不需要返回值。同时这个 kata 也提出了 空节点 的概念。空节点会用于目标链表为空的情况（为了保持引用），在函数执行之后，目标链表会由空节点变成一个包含一个节点的链表。

你可以使用第一个 kata 的 push 方法。

最优的方案

这个算法考的是对链表节点的插入和删除。基本只对 source 和 dest 分别做一次操作，所以不用区分递归和循环。大致思路为：

对 source 做删除一个节点的操作。如果只有一个节点就直接置空。如果有多个节点，就把第二个节点的值赋给头节点，然后让头结点指向第三个节点。

对 dest 做插入一个节点的操作。如果头结点为空就直接赋值，否则把头结点复制一份，作为第二个节点插入到链表中，再把新值赋给头结点。

代码如下：

function moveNode(source, dest) {
  if (!source || !dest || source.data === null) throw new Error("invalid arguments")

  const data = source.data

  if (source.next) {
    source.data = source.next.data
    source.next = source.next.next
  } else {
    source.data = null
  }

  if (dest.data === null) {
    dest.data = data
  } else {
    dest.next = new Node(dest.data, dest.next)
    dest.data = data
  }
}

递归方案

这是我最开始思考的方案，差别在于对 dest 如何插入新节点的处理上用了递归。思路是把所有节点的 data 往后移一位，即把新值赋给第一个节点，第一个节点的值赋给第二个节点，第二个节点的值赋给第三个节点，以此类推。但实际操作中的顺序必须是反的，就是把倒数第二个节点的值赋给最后一个节点，倒数第三个节点的值赋给倒数第二个节点…… 这个思路对 dest 操作了 N 次，不如上一个解法的 1 次操作高效。不过也算是个有意思的递归用例，所以我仍然把它放了上来。

代码如下，主要看 pushInPlaceV2 ：

function moveNodeV2(source, dest) {
  if (source === null || dest === null || source.isEmpty()) {
    throw new Error("invalid arguments")
  }

  pushInPlaceV2(dest, source.data)

  if (source.next) {
    source.data = source.next.data
    source.next = source.next.next
  } else {
    source.data = null
  }
}

function pushInPlaceV2(head, data) {
  if (!head) return new Node(data)

  if (!head.isEmpty()) head.next = pushInPlaceV2(head.next, head.data)
  head.data = data
  return head
}

总结

总是使用递归会产生惯性，导致忽略了数据结构的基本特性。链表的特性就是插入和删除的便利，改改引用就成了。

算法相关的代码和测试我都放在 GitHub 上，如果对你有帮助请帮我点个赞！

参考资料

Codewars Kata
GitHub 的代码实现
GitHub 的测试

云服务器 GPU云服务器用javascript操作xml 多链表c语言实现 java实现链表插入遍历c语言实现链表

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/81149.html

用 JavaScript 实现链表操作 - 前言和目录

摘要：我打算写一个链表操作的系列，来自的系列，实现语言是。通过自己实现一个链表和常用操作，可以加深理解这类数据结构的优缺点。链表经常用来训练指针操作，虽然这只对适用，但等高级语言中控制引用的思路其实也差不多。 TL;DR 我打算写一个链表操作的系列，来自 Codewars 的 Linked List 系列 kata ，实现语言是 JavaScript 。这篇是开篇，简单描述了一下我写这个的目...

BetaRabbit 2019-08-20 12:25 评论0 收藏0
用 JavaScript 实现链表操作 - 09 Move Node

摘要：需求实现一个函数，把源链表的头节点移到目标链表。当源链表为空时函数应抛出异常。为了简化起见，我们会用一个对象来存储改变后的源链表和目标链表的引用。它也是函数的返回值。解法配合，这个非常简单，注意这个函数没有改变两个链表本身。 TL;DR 把一个链表的首节点移到另一个链表。系列目录见前言和目录。需求实现一个 moveNode() 函数，把源链表的头节点移到目标链表。当源链表为空时...

suosuopuo 2019-08-20 13:35 评论0 收藏0
用 JavaScript 实现链表

摘要：相反，双向链表具有指向其前后元素的节点。另外，可以对链表进行排序。这个实用程序方法用于打印链表中的节点，仅用于调试目的。第行将更新为，这是从链表中弹出最后一个元素的行为。如果链表为空，则返回。 showImg(https://segmentfault.com/img/bVbsaI7?w=1600&h=228); 什么是链表单链表是表示一系列节点的数据结构，其中每个节点指向链表中的下一...

appetizerio 2019-08-26 13:51 评论0 收藏0
[LintCode] Insertion Sort List

摘要：插入排序维基百科一般来说，插入排序都采用在数组上实现。在放这个数之前，这个数的目标位置和原始位置之间的数都要先进行后移。最后，当，即遍历完整个原链表之后，新链表排序完成。 Problem Sort a linked list using insertion sort. Example Given 1->3->2->0->null, return 0->1->2->3->null. No...

wzyplus 2019-08-14 15:21 评论0 收藏0
JavaScript数据结构和算法

摘要：栈被称为一种后入先出的数据结构。散列使用的数据结构叫做散列表。这些操作需要求助于其他数据结构，比如下面介绍的二叉查找树。前言在过去的几年中，得益于Node.js的兴起，JavaScript越来越广泛地用于服务器端编程。鉴于JavaScript语言已经走出了浏览器，程序员发现他们需要更多传统语言（比如C++和Java）提供的工具。这些工具包括传统的数据结构（如链表，栈，队列，图等），...

EastWoodYang 2019-08-21 16:23 评论0 收藏0