如何在Ruby中实现链表的合并排序
在Ruby中实现链表的合并排序可以通过以下步骤完成：
- 定义链表节点类：首先，我们需要定义一个链表节点类，包含一个值属性和一个指向下一个节点的指针属性。可以使用Ruby的类来实现这个节点类。
class ListNode
attr_accessor :value, :next
def initialize(value)
@value = value
@next = nil
end
end- 创建链表：接下来，我们可以根据给定的数组创建两个链表。一个链表用于存储待排序的元素，另一个链表用于存储排序后的元素。
def create_linked_list(arr)
head = ListNode.new(arr[0])
current = head
(1...arr.length).each do |i|
node = ListNode.new(arr[i])
current.next = node
current = node
end
head
end- 合并排序：实现链表的合并排序算法。这里可以使用递归的方式来实现。
def merge_sort(head)
return head if head.nil? || head.next.nil?
mid = find_middle(head)
left = head
right = mid.next
mid.next = nil
merge(merge_sort(left), merge_sort(right))
end
def find_middle(head)
slow = head
fast = head
while fast.next && fast.next.next
slow = slow.next
fast = fast.next.next
end
slow
end
def merge(left, right)
dummy = ListNode.new(0)
current = dummy
while left && right
if left.value < right.value
current.next = left
left = left.next
else
current.next = right
right = right.next
end
current = current.next
end
current.next = left if left
current.next = right if right
dummy.next
end- 测试：最后，我们可以创建一个测试函数来验证链表的合并排序算法是否正确。
def test_merge_sort(arr)
head = create_linked_list(arr)
sorted_head = merge_sort(head)
print_linked_list(sorted_head)
end
def print_linked_list(head)
current = head
while current
print "#{current.value} "
current = current.next
end
puts
end
test_merge_sort([4, 2, 1, 3]) # 输出：1 2 3 4通过以上步骤，我们可以在Ruby中实现链表的合并排序算法。这个算法的时间复杂度为O(nlogn)，其中n是链表的长度。在实际应用中，链表的合并排序可以用于对大量数据进行排序，例如日志文件的排序、搜索引擎的排名等。
腾讯云相关产品和产品介绍链接地址：
- 云服务器（CVM）：https://cloud.tencent.com/product/cvm
- 云数据库 MySQL 版（CMYSQL）：https://cloud.tencent.com/product/cmysql
- 人工智能平台（AI Lab）：https://cloud.tencent.com/product/ailab
- 云存储（COS）：https://cloud.tencent.com/product/cos
- 区块链服务（Tencent Blockchain）：https://cloud.tencent.com/product/tencentblockchain
相关·内容
1回答
Java，函数不能识别返回语句
java、loops、if-statement、linked-list、return
在编写检查链表是否是伪随机链表的代码时，我创建了一个返回反向链表的reverseLL函数和一个返回循环内返回语句的isPallindrome函数check.The问题是没有检测到循环内的返回语句，并且每次都只执行返回true的最后一条语句:我正在检查LL是否是伪随机链表，方法是将其分成两部分并反转后半部分，然后比较这两部分
public static Node<Integer> reverseLL(Node<Integer> head){
Node<Integer> prev = null;
Node<Integer> curre
浏览 15提问于2020-02-04得票数 2
回答已采纳
2回答
算法:将排序与链表缺失项合并
java、algorithm、sorting
我正在尝试用合并排序来排序我的链接列表。这个列表实际上是排序的，但是它有点缺少第一项。
合并排序功能：
public Node mergeSort(Node head) {
if (head == null || head.next == null) {
return head;
}
Node middle = middleElement(head);
Node nextofMiddle = middle.next;
middle.next = null;
return merge(mergeSort(head), mergeS
浏览 0提问于2018-04-21得票数 1
回答已采纳
2回答
如何清除此AttributeError的"nonetype"？
python、attributeerror、nonetype
在编译这个合并排序链表时，我正在学习数据结构。我得到了这个错误。我试了这么多，但是没有效果。有人能告诉我出了什么问题吗？求求你。 回溯(最近一次调用)：File "C:\Users**\AppData\Local\Programs\Python\Python37\merge_sort_ver_2.0 linked list.py"，第122行，在 sorted_list=merge_sort(lst) File "C:\Users**\AppData\Local\Programs\Python\Python37\merge_sort_ver_2.0 link
浏览 38提问于2021-08-28得票数 0
回答已采纳
1回答
重新排列LinkedList，产生无休止的端点
python、linked-list
我现正研究重新安排有关名单的问题。代码的逻辑感觉是正确的，但是我会重复链表中无穷无尽的点。我不知道原因，但更有可能的是，链接列表的定义有问题。问题是：
给出了单个LinkedList的头，编写了修改LinkedList的方法，使来自LinkedList下半部分的节点以相反的顺序插入到节点的上半部分。因此，如果LinkedList具有节点1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null，则您的方法应该返回1 -> 6 -> 2 -> 5 -> 3 -> 4 -> null。
您的算法不应该使用任何额外的空
浏览 2提问于2020-12-18得票数 1
2回答
减去链接列表节点
algorithm、optimization、data-structures、linked-list
我正试图解决一个链接列表问题。给定一个单链接列表，修改前半个节点的值，以便：
第一个节点的新值=最后一个节点的值-第一个节点的当前值
第二个节点的新值=第二个最后一个节点的值-第二个节点的当前值
例子：
给定链表1 -> 2 -> 3 -> 4 -> 5，
您应该返回4 -> 2 -> 3 -> 4 -> 5
到目前为止我能想到的解决方案是
迭代链接列表以找到长度。
迭代链接列表的后半部分，将节点值推到堆栈中。
迭代列表的前半部分，弹出堆栈，减去节点值。
也许这是最天真的解决方案。能否从时间/空间的角度提出更有效的解决方案(希
浏览 1提问于2016-11-15得票数 2
回答已采纳
1回答
单链表在Python中的实现
python、linked-list、reinventing-the-wheel
我正在学习Python中的基本数据结构。如果我的实现没有问题，或者我忽略了任何一个角落的情况，我就没有足够的信心。因此，请检查我的代码单链表，并让我知道我可以改进。
"""
Singly Linked List Implementation
"""
class Node:
"""
Constructor for Node class
takes 3 arguments. 'value' for Node's value and 'next' for n
浏览 0提问于2022-01-16得票数 6
4回答
最快的方法证明链表是循环的？巨蟒
python、algorithm、data-structures、linked-list
有人能告诉我证明链表包含循环的最佳方法吗？我用的是两个指针的算法，一个用一个步骤移动慢，一个用两个步骤移动得更快。
class Node(object):
def __init__(self, value, next=None):
self.next=next
self.value=value
def create_list():
last = Node(8)
head = Node(7, last)
head = Node(6, head)
head = Node(5, head)
head = Node(4,
浏览 2提问于2013-12-03得票数 4
回答已采纳
2回答
单链表排序算法中的递归错误
python、sorting、recursion、linked-list
我一直试图用Python为单链接列表编写一个mergeSort算法，对于更大的列表，在函数合并(p1，p2)中，我一直收到一个关于达到最大递归深度的错误：“相对地超过了最大递归深度”。我试图在没有递归的情况下编写这个函数，它可以工作，但我也想尝试一下。我找不到我犯了什么错误，如果有人能给我指明正确的方向，我会很高兴的。
节点类：
class Node():
def __init__(self):
self.data=None
self.next=None
合并排序：
def merge(p1,p2):
if p2 == None:
浏览 9提问于2022-03-12得票数 0
2回答
在python的链接列表中，我混淆了当前和current.next之间的关系。我们什么时候应该使用它们？
python、linked-list
在链接列表中，我将这两个类用于Node和LinkedList。现在，当在链表中为不同的操作添加不同的方法时，我们需要使用when循环。我们通常使用、current =self.head、或while current.next:来迭代语句。我很困惑这两种情况是如何不同的，以及它如何影响循环。这两种情况有什么区别吗？
class Node(object):
def __init__(self, value):
self.value = value
self.next = None
class LinkedList(object):
def
浏览 4提问于2021-07-08得票数 0
2回答
C跟踪中的单链接列表合并排序
c、sorting、linked-list、mergesort
(参见初始迭代。)
继续从合并排序C中的单链列表，我合并了@vnp提出的观点。
现在看起来是这样的：
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
typedef struct linked_list_node {
int value;
struct linked_list_node* next;
} linked_list_node;
/****************************************************************
浏览 0提问于2016-08-11得票数 3
回答已采纳
7回答
使用Java在链表上递归MergeSort
java、algorithm、recursion、linked-list、mergesort
我在网络上搜索一个好的、干净的、简单的Java合并排序算法的实现，以找到一个使用递归的链接列表。
我找不到好的，所以我试着在这里实现它。但我被困住了。
以下是我到目前为止所拥有的：
public List mergeSortList(Node head, Node tail) {
if ((head == null) || (head.next == null))
return;
Node middle = this.findMiddle(head);
List left = mergeSortList(this.head, middle);
浏览 2提问于2013-11-17得票数 1
回答已采纳
2回答
如何删除链表中的节点？
python、data-structures、linked-list
我正在使用Python实现链表。以下是我的代码
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, head = None):
self.head = head
def append(self, newElement):
current = self.head
if self.head:
whi
浏览 15提问于2019-07-22得票数 1
2回答
如何从合并排序中获取O(n log(n))？
c#、algorithm、sorting、mergesort
如何在链接列表上使用合并排序实现中使用O(nlog(n))。我应该向O(nlog(n))输入什么，以知道我在合并排序上实现的时间。
public static LinkedListNode<T> MergeSortLL<T>(LinkedListNode<T> Head) where T : IComparable<T>
{
if (Head?.Next == null)
{
return Head;
}
var middle = GetMiddle(Head);
var half = m
浏览 1提问于2016-02-15得票数 2
回答已采纳
2回答
Javascript中链表与数组的比较
javascript、algorithm、data-structures、linked-list
因此，我在JS中尝试了一下链表，并提出了以下问题：
假设我们有一个数组和一个链表，它们都有5000个元素。我们想在索引10处插入新元素。数组方法非常简单。我们在给定的索引处插入新元素，并将其余元素向前移动一个索引。所以我试着用链表来做这件事，并以下面的代码结束：
从获取链表的实现，并添加额外的方法addOnPosition(数据，索引)。下面是代码：
function LinkedList() {
this._head = null;
this._length = 0;
}
LinkedList.prototype = {
constructor: LinkedList,
add: fu
浏览 2提问于2013-08-26得票数 7
回答已采纳
3回答
双链接列表-更新列表->合并排序后的尾
c、linked-list、mergesort
在双链接列表的实现中，我使用了典型的结构：
struct node
{
void *data;
struct node *prev;
struct node *next;
};
我还将在列表末尾插入O(1)时间，因此我有另一个struct存储head和tail
struct linklist
{
struct node *head;
struct node *tail;
size_t size;
};
该程序适用于所有insert和delete操作，但排序函数有问题，我正在使用合并排序算法，因为我知道排序列表是最有效或最有效的算法之一，该算法运行
浏览 10提问于2020-05-30得票数 3
回答已采纳
1回答
如何编写从链表中移除特定对象的方法？
c#、methods、linked-list
我没有成功地从链表中删除特定的项，方法是- public void removeFromList(string item remove，LinkedList List)。
如何编写从链表中移除特定项的方法？
我的代码是：
public class Node
{
public Node next; //saves the adress
public Person data; //saves the person
}
public class LinkedList
{
private Node head; //starts from the begging
浏览 1提问于2015-09-18得票数 0
2回答
帮助对列表中的节点进行排序
c#、list、sorting
我目前正在使用C#中的通用链表，我需要对列表中的节点进行排序。
namespace ConsoleApplication1
{
// T is the type of data stored in a particular instance of GenericList.
public class GenericList<T>
{
private class Node
{
// Each node has a reference to the next node in the list.
public Node Next;
浏览 0提问于2011-03-18得票数 0
1回答
找出此函数中使用的排序算法
sorting、data-structures、doubly-linked-list
嗨，有人能帮我弄清楚这个函数用的是哪种排序算法吗？ public void sortList() {
Node current = null, index = null;
int temp;
//Check whether list is empty
if(head == null) {
return;
}
else {
//Current will point to head
for(cu
浏览 12提问于2020-04-22得票数 0
回答已采纳
2回答
按组反转链接列表
python、recursion、linked-list、reverse
我现在正努力倒转一份分组链接的清单，但遇到了一些问题。
问题是：
给定具有‘n’节点的LinkedList，根据其大小以下列方式反转它：
如果‘n’是偶数，则在n/2节点组中反转列表。如果n是奇数，则保持中间节点不变，反转第一个‘n/2’节点，反转最后一个‘n/2’节点。
我的方法是：
def lenLinkedlist(head):
count = 0
current = head
while current:
current = current.next
count += 1
return count
def rev
浏览 1提问于2021-01-07得票数 1
1回答
如何跳过中间节点？
python、linked-list
我正在尝试为链表编写代码，以便它删除链表中的节点，它可以是链表中除第一个和最后一个节点之外的任何节点。我在下面提出了一些想法。 我不确定如何完成它，我知道在while循环中需要一些对k的引用，以便我们在遍历链表时跳过节点，但是我如何引用这个k呢？我会做一个'for i in range k'，然后在第k次迭代中执行跳过吗？ def delete_middle(l1,k):
if l1.head is None:
return None
current = l1.head
while current:
if curr
浏览 15提问于2021-01-31得票数 0
回答已采纳
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
实时音视频
对象存储
即时通信 IM活动推荐
腾讯云开发者
