2

私は2つのソートされたリンクリストのマージを試みていました.

コード スニペットは、以下の 2 つのリストでは機能しません。

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

8 に答える 8

7

n1または のいずれかn2が先に枯渇したときのために、さらに 2 つの条件を追加する必要があります。したがって、条件 -n1 != null && n2 != nullは、両方のリストが同じサイズの場合にのみ機能します。

以下の 2 つの条件のコードを追加するだけです。

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渡されたノードの 1 つを拡張するだけです。

以下のようにメソッドを変更できます。

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;
    }
}
于 2013-07-19T11:50:28.713 に答える
1 
if(n1 != null && n2 != null) {

リストの 1 つが null で、もう 1 つがそうでない場合はどうなりますか?

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);
}
于 2013-07-19T11:51:46.623 に答える
0

最適化もできます。理解のためだけに

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;
    }
于 2013-07-19T11:58:35.887 に答える
0 
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);
    }
}
于 2013-10-17T20:44:16.667 に答える
0

これは、2 つの並べ替えられたリンク リストをマージするための簡単で反復的な (再帰的でない) コードです。

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);
        }
}
于 2016-02-22T16:48:09.400 に答える