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

Merging two sorted linked list of unequal length

提问by tmgr

I was trying out the merging of two sorted linked list.

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

The code snippet doesn't work for below two list :

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

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

But the output for below programs turns out to be this :

但以下程序的输出结果是这样的：

Output :  1->2->3->4->5->6->7->8->9->null // element 10 is missing.

Am I missing something ? Live Demo : http://ideone.com/O7MBlo

我错过了什么吗？现场演示：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));
    }
}

回答by Rohit Jain

You need to add two more conditions, for when either n1or n2exhausts earlier. So, your condition - n1 != null && n2 != null, will only work in the case when both the list are of same size.

您需要再添加两个条件，即 whenn1或n2更早耗尽。因此，您的条件 -n1 != null && n2 != null仅适用于两个列表大小相同的情况。

Just add code for below two conditions, after that if:

只需为以下两个条件添加代码，之后如果：

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

---

---

Actually, you don't needto build a new resultlist there. You can simply extend one of the passed Nodes.

实际上，您不需要在result那里构建新列表。您可以简单地扩展传递的节点之一。

You can modify your method as below:

您可以修改您的方法如下：

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

回答by rahulserver

A recursive algorithm has a base condition.So your base condition are:

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

• empty list n1 and n2
• n1 empty and n2 not empty.
• n2 empty and n1 empty.

• 空列表 n1 和 n2
• n1 为空，n2 不为空。
• n2 空，n1 空。

Handle your base conditions 2 and 3 well as:

处理您的基本条件 2 和 3：

In condition 2, base condition is n2 empty so we will return n1:

在条件 2 中，基本条件为 n2 为空，因此我们将返回 n1：

else if(n1!=null ){
        result=n1;
    }

In condition 3, base condition is n1 empty so we will return n2:

在条件 3 中，基本条件为 n1 为空，因此我们将返回 n2：

else if(n2!=null ){
        result=n2;
    }

Hence problem is in design of your base conditions in algorithm!!

因此，问题在于算法中的基本条件设计！！

So try this, it surely works

所以试试这个，它肯定有效

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

Good luck!!

祝你好运！！

Edit: Thislink should help you in designing recursive algorithms.

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

回答by Girish Rathi

Solution for Merge Two Sorted linkedlist: https://leetcode.com/problems/merge-two-sorted-lists/

合并两个排序链表的解决方案：https://leetcode.com/problems/merge-two-sorted-lists/

While loop will execute till one of the list finish , remaining data of another list will append later outside the while loop.

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

回答by tafa

if(n1 != null && n2 != null) {

What happens when one of the lists is null but the other one is not?

当其中一个列表为空而另一个不是时会发生什么？

It returns null. But instead it should return the list that is not null.

它返回空值。但它应该返回不为空的列表。

A possible solution would be like;

一个可能的解决方案是这样的；

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

回答by Karthikeyan

It can be optimized too. Just for understanding

也可以优化。只为了解

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

回答by james liao

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

回答by Ankur Lathiya

Here is Easy and Iterative (non recursive) code for merge two sorted Linked List:

这是用于合并两个排序链表的简单迭代（非递归）代码：

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

回答by Ankur Lathiya

Merge Two Sorted Lists | Leetcode problem | Javascript Solution

合并两个排序列表 | 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));