java合并两个长度不等的排序链表

Question

我正在尝试合并两个排序的链表

代码段不适用于以下两个列表：

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));
    }
}

Answer 1

您需要再添加两个条件，用于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;
    }
}

Answer 2

它也可以被优化。只是为了理解

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;
    }

Answer 3

合并两个已排序linkedlist的解决方案： 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;
        }
    }

Answer 4

递归算法有一个基本条件。所以你的基本条件是：

• 空列表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;
}

祝你好运

编辑：This链接应该可以帮助您设计递归算法

Answer 5

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);
    }
}

Answer 6

if(n1 != null && n2 != 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);
}