我正在尝试合并两个排序的链表。
代码片段不适用于以下两个列表：
List 1 : 1->3->5->7->9->null
List 2 : 2->4->6->8->10->null
Expected List : 1->2->3->4->5->6->7->8->9->10->null
但以下程序的输出结果是：
Output : 1->2->3->4->5->6->7->8->9->null // element 10 is missing.
我是不是错过了什么？现场演示：http://ideone.com/O7MBlo
class Node {
Node next;
int value;
Node(int val) {
this.value = val;
this.next = null;
}
@Override
public String toString() {
Node cur = this;
String str = "";
while(cur != null) {
str += cur.value+"->";
cur = cur.next;
}
return str;
}
}
class MergeLL {
public static Node merge(Node n1, Node n2) {
Node result = null;
if(n1 != null && n2 != null) {
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
}
return result;
}
public static void main(String[] args) {
Node n1 = new Node(1);
Node n3 = new Node(3);
Node n5 = new Node(5);
Node n7 = new Node(7);
Node n9 = new Node(9);
n1.next = n3;
n3.next = n5;
n5.next = n7;
n7.next = n9;
n9.next = null;
Node n2 = new Node(2);
Node n4 = new Node(4);
Node n6 = new Node(6);
Node n8 = new Node(8);
Node n10 = new Node(10);
n2.next = n4;
n4.next = n6;
n6.next = n8;
n8.next = n10;
n10.next = null;
System.out.println("Merge : " + merge(n1, n2));
}
}
您需要再添加两个条件，用于n1或n2较早耗尽时。因此，您的条件n1 != null && n2 != null仅在两个列表大小相同的情况下有效。
只需添加以下两种情况的代码，之后如果：
if(n1 != null && n2 != null) {
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
} else if (n1 != null) {
result = n1; // Add all the elements of `n1` to `result`
} else if (n2 != null) {
result = n2; // Add all the elements of `n2` to `result`
}
实际上，您不需要在那里构建一个新的result列表。您可以简单地扩展其中一个传递的节点。
您可以修改您的方法如下：
public static Node merge(Node n1, Node n2) {
if (n1 == null) return n2;
if (n2 == null) return n1;
if (n1.value < n2.value) {
n1.next = merge(n1.next, n2);
return n1;
} else {
n2.next = merge(n2.next, n1);
return n2;
}
}
递归算法有一个基本条件。所以你的基本条件是：
- 空列表n1和n2
- n1为空，n2不为空
- n2为空，n1为空
处理您的基本条件2和3以及：
在条件2中，基本条件为n2为空，因此我们将返回n1:
else if(n1!=null ){
result=n1;
}
在条件3中，基本条件n1为空，因此我们将返回n2:
else if(n2!=null ){
result=n2;
}
所以问题是在算法中设计你们的基本条件！！
所以试试这个，它肯定有效
public static Node merge(Node n1, Node n2) {
Node result = null;
if(n1 != null && n2 != null) {
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
}
else if(n1!=null ){
result=n1;
}
else if(n2!=null){
result=n2;
}
return result;
}
祝你好运！！
编辑：此链接将帮助您设计递归算法。
if(n1 != null && n2 != null) {
当其中一个列表为空而另一个列表不为空时会发生什么？
它返回null。但是它应该返回不为null的列表。
可能的解决方案如下：；
if(n1 == null)
return n2;
if(n2 == null)
return n1;
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
合并双排序链表的解决方案：https://leetcode.com/problems/merge-two-sorted-lists/
While循环将执行到其中一个列表完成，另一个列表的剩余数据稍后将附加到While循环之外。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dummy = new ListNode(0);
ListNode head = dummy;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
dummy.next = l1;
l1 = l1.next;
}else{
dummy.next = l2;
l2 = l2.next;
}
dummy = dummy.next;
}
if(l1 != null) {
dummy.next = l1;
}else {
dummy.next = l2;
}
return head.next;
}
}
它也可以进行优化。只是为了理解
public static Node merge(Node n1, Node n2) {
Node result = null;
if(n1 != null && n2 != null) {
if(n1.value < n2.value) {
result = n1;
result.next = merge(n1.next, n2);
} else {
result = n2;
result.next = merge(n1, n2.next);
}
}
else if(n1 != null) {
result = n1;
result.next = merge(n1.next, n2);
}
else if(n2 != null) {
result = n2;
result.next = merge(n1, n2.next);
}
return result;
}
package test;
import java.util.*;
public class TestMergeLists<T extends Comparable<? super T>>
{
static <T extends Comparable<? super T>> List<T> merge(List<T> a,List<T>b)
{
Collections.sort(a);
Collections.sort(b);
List<T> result = new ArrayList<T>();
int i = 0;
int j = 0;
for (;;)
{
T a1 = a.get(i);
T b1 = b.get(j);
if (a1.compareTo(b1) > 0)
{
result.add(b1);
j++;
if (j == b.size())// no more
{
if (i < a.size() - 1)
result.addAll(a.subList(i + 1, a.size()));
break;
}
} else if (a1.compareTo(b1) == 0)
{
result.add(a1);
result.add(b1);
i++;
if (i == a.size())
{
if (j < b.size() - 1)
result.addAll(b.subList(j + 1, b.size()));
break;
}
j++;
if (j == b.size())// no more
{
if (i < a.size() - 1)
result.addAll(a.subList(i + 1, a.size()));
break;
}
} else
{
result.add(a1);
i++;
if (i == a.size())// no more
{
if (j < b.size() - 1)
result.addAll(b.subList(j + 1, b.size()));
break;
}
}
}
return result;
}
public static void main(String args[])
{
List<String> a = new ArrayList<String>();
a.addAll(Arrays.asList("the statement you found confusing is how MergeSort merges two ".split(" ")));
List<String> b = new ArrayList<String>();
b.addAll(Arrays.asList("then increment the current index for ".split(" ")));
List<String> result = merge(a,b);
System.out.println(result);
}
}
以下是用于合并两个排序链表的简单迭代（非递归）代码：
import java.util.*;
class Node
{
public int data;
public Node next;
Node(int x)
{
data=x;
next=null;
}
}
public class Test {
public static Node merge(Node a, Node b)
{
Node res=null;
Node first=null;
if(a.data < b.data)
{
res=a;
first=a;
a=a.next;
}
else
{
first=b;
res=b;
b=b.next;
}
while(a!=null && b!=null)
{
if(a.data < b.data)
{
res.next=a;
res=res.next;
a=a.next;
}
else
{
res.next=b;
res=res.next;
b=b.next;
}
}
if(a!=null)
{
res.next=a;
}
else if(b!=null)
{
res.next=b;
}
return first;
}
public static void display(Node first)
{
while(first!=null)
{
System.out.print(first.data+" ");
first=first.next;
}
}
public static void main(String[] args)
{
Node n1=new Node(4);
Node n2=new Node(5);
Node n3=new Node(7);
Node n4=new Node(10);
n1.next=n2;
n2.next=n3;
n3.next=n4;
n4.next=null;
Node n5=new Node(3);
Node n6=new Node(6);
Node n7=new Node(9);
Node n8=new Node(15);
n5.next=n6;
n6.next=n7;
n7.next=n8;
n8.next=null;
Node f = merge(n1,n5);
display(f);
}
}
合并两个排序列表| Leetcode问题| Javascript解决方案
class ListNode {
constructor(val, next=null) {
this.val = val;
this.next = next;
}
}
const c = new ListNode(4);
const b = new ListNode(2, c);
const a = new ListNode(1, b);
const z = new ListNode(3);
const y = new ListNode(2, z);
const x = new ListNode(1, y);
var mergeTwoLists = function(l1, l2) {
let p1 = l1;
let p2 = l2;
let l3, p3;
if(l1) {
if (l2){
if(p1.val < p2.val) {
l3 = new ListNode(p1.val);
p1 = p1.next;
} else {
l3 = new ListNode(p2.val);
p2 = p2.next;
}
} else {
return l1;
}
} else if(l2) {
return l2;
} else {
return "";
}
p3 = l3;
while(p1 && p2) {
if(p1.val < p2.val) {
p3.next = new ListNode(p1.val);
p1 = p1.next;
} else {
p3.next = new ListNode(p2.val);
p2 = p2.next;
}
p3 = p3.next;
}
if (p1) {
p3.next = p1;
} else {
p3.next = p2;
}
return l3;
}
console.log(mergeTwoLists(a, x));