合并两个单独排序的链表，新列表排序规则不变☆☆☆
问题：
您有两个已经排序的单链接列表，您必须将它们合并并返回新列表的头，而无需创建任何新的额外节点。返回的列表也应排序。
方法签名为：
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将是输出列表。
可能有两种解决方案：
- 递归方法是
- 在传递的两个节点中，使该节点的值较小
- 将较小的节点指向第二个链表中剩余的下一个较小的值
- 返回当前节点（这是传递给该方法的两个节点中的较小者）
- 迭代方法对于所有实际目的都更好，因为列表的大小会随着规模的增加而扩大：
- 将其中一个排序的链表视为列表，将另一个排序的链表视为“节点袋”。
- 然后我们在列表中查找给定节点（从节点包中）的正确位置。
复杂度分析：
时间复杂度：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小站 » 合并两个单独排序的链表，新列表排序规则不变☆☆☆
1. 本站资源转自互联网，源码资源分享仅供交流学习，下载后切勿用于商业用途，否则开发者追究责任与本站无关!
2. 本站使用「署名 4.0 国际」创作协议，可自由转载、引用，但需署名原版权作者且注明文章出处
3. 未登录无法下载，登录使用金币下载所有资源。
IT小站 » 合并两个单独排序的链表，新列表排序规则不变☆☆☆
常见问题FAQ
- 没有金币/金币不足 怎么办？
- 本站已开通每日签到送金币，每日签到赠送五枚金币，金币可累积。
- 所有资源普通会员都能下载吗？
- 本站所有资源普通会员都可以下载，需要消耗金币下载的白金会员资源，通过每日签到，即可获取免费金币，金币可累积使用。
