合并两个单独排序的链表,新列表排序规则不变☆☆☆

作者 : IT 大叔 本文共1813个字,预计阅读时间需要5分钟 发布时间: 2020-10-13

主题链表

问题:

您有两个已经排序的单链接列表,您必须将它们合并并返回新列表的头,而无需创建任何新的额外节点。返回的列表也应排序。

方法签名为:

Node MergeLists(Node list1, Node list2);

节点类如下:

class Node{
   int data;
   Node next;
}

例:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

解:

这是有关如何合并两个排序的链表A和B的算法

while A not empty or B not empty:
   if first element of A < first element of B:
      remove first element from A
      insert element into C
   end if
   else:
      remove first element from B
      insert element into C
end while

这里C将是输出列表。

可能有两种解决方案:

  • 递归方法
    1. 在传递的两个节点中,使该节点的值较小
    2. 将较小的节点指向第二个链表中剩余的下一个较小的值
    3. 返回当前节点(这是传递给该方法的两个节点中的较小者)
  • 迭代方法对于所有实际目的都更好,因为列表的大小会随着规模的增加而扩大:
    1. 将其中一个排序的链表视为列表,将另一个排序的链表视为“节点袋”。
    2. 然后我们在列表中查找给定节点(从节点包中)的正确位置。

复杂度分析:

时间复杂度:O(n)

递归和迭代解决方案的运行时复杂度为或。O(n)

实现方式:

爪哇

递归解决方案:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  if (list1.data < list2.data) {
    list1.next = MergeLists(list1.next, list2);
    return list1;
  } else {
    list2.next = MergeLists(list2.next, list1);
    return list2;
  }
}

避免递归以避免分配新节点:

Node MergeLists(Node list1, Node list2) {
  if (list1 == null) return list2;
  if (list2 == null) return list1;

  Node head;
  if (list1.data < list2.data) {
    head = list1;
  } else {
    head = list2;
    list2 = list1;
    list1 = head;
  }
  while(list1.next != null) {
    if (list1.next.data > list2.data) {
      Node tmp = list1.next;
      list1.next = list2;
      list2 = tmp;
    }
    list1 = list1.next;
  } 
  list1.next = list2;
  return head;
}

Y

递归:

def merge_lists(h1, h2):
    if h1 is None:
        return h2
    if h2 is None:
        return h1

    if (h1.value < h2.value):
        h1.next = merge_lists(h1.next, h2)
        return h1
    else:
        h2.next = merge_lists(h2.next, h1)
        return h2

迭代式:

def merge_lists(head1, head2):
    if head1 is None:
        return head2
    if head2 is None:
        return head1

    # create dummy node to avoid additional checks in loop
    s = t = node() 
    while not (head1 is None or head2 is None):
        if head1.value < head2.value:
            # remember current low-node
            c = head1
            # follow ->next
            head1 = head1.next
        else:
            # remember current low-node
            c = head2
            # follow ->next
            head2 = head2.next

        # only mutate the node AFTER we have followed ->next
        t.next = c          
        # and make sure we also advance the temp
        t = t.next

    t.next = head1 or head2

    # return tail of dummy node
    return s.next
免责声明:
1. 本站资源转自互联网,源码资源分享仅供交流学习,下载后切勿用于商业用途,否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议,可自由转载、引用,但需署名原版权作者且注明文章出处
3. 未登录无法下载,登录使用金币下载所有资源。
IT小站 » 合并两个单独排序的链表,新列表排序规则不变☆☆☆

常见问题FAQ

没有金币/金币不足 怎么办?
本站已开通每日签到送金币,每日签到赠送五枚金币,金币可累积。
所有资源普通会员都能下载吗?
本站所有资源普通会员都可以下载,需要消耗金币下载的白金会员资源,通过每日签到,即可获取免费金币,金币可累积使用。

发表评论