首页 > 试题广场 > 合并两个排序的链表
[编程题]合并两个排序的链表
输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。

1220个回答

添加回答
在单独申请两个指针一个指向新的链表的头结点,一个作为标记位,指向新的链表的尾结点
发表于 2019-05-16 01:34:46 回复(2)
更多回答
递归版本:
 public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        if(list1.val <= list2.val){
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            list2.next = Merge(list1, list2.next);
            return list2;
        }        
    }
非递归版本:
if(list1 == null){
            return list2;
        }
        if(list2 == null){
            return list1;
        }
        ListNode mergeHead = null;
        ListNode current = null;      
        while(list1!=null && list2!=null){
            if(list1.val <= list2.val){
                if(mergeHead == null){
                   mergeHead = current = list1;
                }else{
                   current.next = list1;
                   current = current.next;
                }
                list1 = list1.next;
            }else{
                if(mergeHead == null){
                   mergeHead = current = list2;
                }else{
                   current.next = list2;
                   current = current.next;
                }
                list2 = list2.next;
            }
        }
        if(list1 == null){
            current.next = list2;
        }else{
            current.next = list1;
        }
        return mergeHead;

发表于 2016-07-20 22:26:55 回复(76)
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        //新建一个头节点,用来存合并的链表。
        ListNode head=new ListNode(-1);
        head.next=null;
        ListNode root=head;
        while(list1!=null&&list2!=null){
            if(list1.val<list2.val){
                head.next=list1;
                head=list1;
                list1=list1.next;
            }else{
                head.next=list2;
                head=list2;
                list2=list2.next;
            }
        }
        //把未结束的链表连接到合并后的链表尾部
        if(list1!=null){
            head.next=list1;
        }
        if(list2!=null){
            head.next=list2;
        }
        return root.next;
    }
}

发表于 2016-04-04 14:00:00 回复(42)

合并的过程如图所示,
java代码:
public ListNode Merge(ListNode list1, ListNode list2) {
		if(list1==null)
			return list2;
		if(list2==null)
			return list1;
		ListNode res = null;
		if(list1.val<list2.val){
			res = list1;
			res.next = Merge(list1.next, list2);
		}else{
			res = list2;
			res.next = Merge(list1, list2.next);
		}
		return res;
	}

发表于 2017-01-19 09:39:02 回复(8)
我注释的应该能看懂
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        if(!pHead1)
            return pHead2;
        if(!pHead2)
            return pHead1;
        ListNode* Head;
        ListNode* p;
        //取较小值作头结点
        if(pHead1->val<=pHead2->val){
            Head=pHead1;
            pHead1=pHead1->next;
        }
        else{
            Head=pHead2;
            pHead2=pHead2->next;
        }  
        //开始遍历合并
        p=Head;                                                   //p为合并后的链表的工作指针
        while(pHead1&&pHead2){                       //当有一个链表到结尾时,循环结束
            if(pHead1->val<=pHead2->val){          //如果链表1的结点小于链表2的结点
                p->next=pHead1;                            //取这个结点加入合并链表
                pHead1=pHead1->next;                 //链表1后移一位
                p=p->next;                                      //工作指针后移一位
            }               
            else{                                               //否则取链表2的结点
                p->next=pHead2;
                pHead2=pHead2->next;
                p=p->next;
            }                
        }
        if(pHead1 == NULL)           //链表1遍历完了
            p->next = pHead2;         //如果链表2也遍历完了,则pHead2=NULL
        if(pHead2 == NULL)            //链表2遍历完了
            p->next = pHead1;         ///如果链表1也遍历完了,则pHead1=NULL
        return Head;
    }
};
发表于 2015-11-29 13:46:38 回复(15)
思路:
  • 比较两个链表的首结点,哪个小的的结点则合并到第三个链表尾结点,并向前移动一个结点。
  • 步骤一结果会有一个链表先遍历结束,或者没有
  • 第三个链表尾结点指向剩余未遍历结束的链表
  • 返回第三个链表首结点

# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        dummy = ListNode(0)
        pHead = dummy
        
        while pHead1 and pHead2:
            if pHead1.val >= pHead2.val:
                dummy.next = pHead2
                pHead2 = pHead2.next
            else:
                dummy.next = pHead1
                pHead1 = pHead1.next
               	
            dummy = dummy.next
        
        if pHead1:
            dummy.next = pHead1
        elif pHead2:
            dummy.next = pHead2
        
        return pHead.next
发表于 2016-07-25 07:31:53 回复(7)
public class Solution {
 public ListNode Merge(ListNode list1, ListNode list2) {
 if(list1==null)
 return list2;
 else if(list2==null)
 return list1;
 ListNode mergeHead=null;
 if(list1.val<list2.val){
 mergeHead=list1;
 mergeHead.next=Merge(list1.next, list2);
 }
 else{
 mergeHead=list2;
 mergeHead.next=Merge(list1, list2.next);
 }
 return mergeHead;

 }
}


发表于 2015-04-17 15:08:36 回复(32)
//做题目的时候还是要训练到位,建议先自己想,并且同时实现递归和非递归版本
//面试的时候一般都会考察。
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* result = NULL;
        ListNode* current = NULL;
        
        if(pHead1 == NULL)
            return pHead2;
        if(pHead2 == NULL)
            return pHead1;
        /*
        if(pHead1->val <= pHead2->val){
            result = pHead1;
            result->next = Merge(pHead1->next, pHead2);
        } else {
            result = pHead2;
            result->next = Merge(pHead1, pHead2->next);
        }
        */
        while(pHead1 != NULL && pHead2 != NULL){
            if(pHead1->val <= pHead2->val){
                if(result == NULL){
                    current = result = pHead1;
                } else {
                    current->next = pHead1;
                    current = current->next;
                }
                pHead1 = pHead1->next;
            } else {
                if(result == NULL){
                    current = result = pHead2;
                } else {
                    current->next = pHead2;
                    current = current->next;
                }
                pHead2 = pHead2->next;
            }
        }
        
        if(pHead1 == NULL){
            current->next = pHead2;
        }
        if(pHead2 == NULL){
            current->next = pHead1;
        }
        
        return result;
    }
};

发表于 2015-08-13 21:00:11 回复(17)
/*
struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};*/
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
        ListNode* node=NULL;
        if(pHead1==NULL){return node=pHead2;}
        if(pHead2==NULL){return node=pHead1;}
        if(pHead1->val>pHead2->val){
            node=pHead2;
            node->next=Merge(pHead1,pHead2->next);
        }else
            {
            node=pHead1;
            node->next=Merge(pHead1->next,pHead2);
        }
        return node;
        
    }
    
};
递归,比较大小插入小的。
发表于 2016-03-31 00:29:20 回复(1)

python solution:


class Solution:

    def Merge(self, pHead1, pHead2):
        # write code here
        res = []
        while pHead1:
            res.append(pHead1.val)
            pHead1 = pHead1.next
        while pHead2:
            res.append(pHead2.val)
            pHead2 = pHead2.next
        res.sort()
        dummy = ListNode(0)
        pre = dummy
        for i in res:
            node = ListNode(i)
            pre.next = node
            pre = pre.next
        return dummy.next
发表于 2017-10-13 21:47:12 回复(14)
//非递归简洁版,傻子都能看懂哦
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newHead = new ListNode(-1);
        ListNode current = newHead;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }
        if (list1 != null) current.next = list1;
        if (list2 != null) current.next = list2;
        return newHead.next;
    }
}
-----------------------------------------------------------------
//递归解法 参考高票答案
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) return list2;
        if (list2 == null) return list1;
        if (list1.val < list2.val) {
            list1.next = Merge(list1.next, list2);
            return list1;
        } else {
            list2.next = Merge(list1, list2.next);
            return list2;
        }
    }
}

编辑于 2017-11-29 10:16:27 回复(7)
Python写法
1. 非递归版本
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        #初始化
        tmp = ListNode(0)
        pHead = tmp        
        while pHead1 and pHead2:
            if pHead1.val < pHead2.val:
                tmp.next = pHead1
                pHead1 = pHead1.next
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
            tmp = tmp.next
        if not pHead1:
            tmp.next = pHead2
        if not pHead2:
            tmp.next = pHead1
        return pHead.next

2. 递归版本
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        if pHead1 is None:
            return pHead2
        if pHead2 is None:
            return pHead1
        if pHead1.val < pHead2.val:
            pHead1.next = self.Merge(pHead1.next,pHead2)
            return pHead1
        else:
            pHead2.next = self.Merge(pHead1,pHead2.next)
            return pHead2

编辑于 2018-09-04 16:24:41 回复(0)
class Solution {
public:
    ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
    {
		if (!pHead1 && !pHead2)return NULL;
		if (!pHead1)return pHead2;
		if (!pHead2)return pHead1;
		ListNode *p = new ListNode(0);
		ListNode *head = p;
		while (pHead1 && pHead2)
		{
			if (pHead1->val < pHead2->val)
			{
				head->next = pHead1;
				pHead1 = pHead1->next;
			}
			else
			{
				head->next = pHead2;
				pHead2 = pHead2->next;
			}
			head = head->next;
		}
		if (pHead1)
			head->next = pHead1;
		if (pHead2)
			head->next = pHead2;
		return p->next;
    }
};

发表于 2016-07-24 00:07:32 回复(3)
/**
 * 题目描述
 * 输入两个单调递增的链表,输出两个链表合成后的链表,当然我们需要合成后的链表满足单调不减规则。
 *
 * @author shijiacheng
 * @date 2018/2/23
 */
public class MergeSortedListsSolution {
    /**
     * 链表1的头结点的值小于链表2的头结点的值,因此链表1的头结点是合并后链表的头结点。
     * 在剩余的结点中,链表2的头结点的值小于链表1的头结点的值,因此链表2的头结点是剩
     * 余结点的头结点,把这个结点和之前已经合并好的链表的尾结点链接起来。
     */
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null) {
            return list2;
        } else if (list2 == null) {
            return list1;
        }
        ListNode mergeNode = null;
        if (list1.val < list2.val) {
            mergeNode = list1;
            mergeNode.next = Merge(list1.next, list2);
        } else {
            mergeNode = list2;
            mergeNode.next = Merge(list1, list2.next);
        }

        return mergeNode;
    }
}
发表于 2018-02-23 16:21:19 回复(0)
# -*- coding:utf-8 -*-
class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
class Solution:
    # 返回合并后列表
    def Merge(self, pHead1, pHead2):
        # write code here
        head = ListNode(0)
        tmp = head
        while pHead1 is not None and pHead2 is not None:
            if pHead1.val <= pHead2.val:
                tmp.next = pHead1
                pHead1 = pHead1.next
            else:
                tmp.next = pHead2
                pHead2 = pHead2.next
            tmp = tmp.next
            
        if pHead1 is None:
            tmp.next = pHead2
        elif pHead2 is None:
            tmp.next = pHead1
            
        return head.next

发表于 2017-07-05 16:18:53 回复(3)
运行通过的Java代码,如下:
/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
     public ListNode Merge(ListNode list1, ListNode list2) {
         if(list1 == null){
             return list2;
         }else if(list2 == null){
             return list1;
         }
         ListNode list = null;
         if(list1.val <= list2.val){
             list = list1;
             list.next = Merge(list1.next,list2);
         }
         if(list2.val < list1.val){
             list = list2;
             list.next = Merge(list1,list2.next);
         }
         return list;
     }
}
编辑于 2015-08-24 16:47:59 回复(1)
//利用递归方法求解
//求解思路:
//首先判断两个表头是否为空,若都为空,则返回NULL;若其中一个为空,返回不为空的那个表头;
//else 比较两个表头关键值的大小,返回具有较小关键值的表头res;
//res->next = Merge(pHead1,pHead2);
ListNode* solution::Merge(ListNode* pHead1, ListNode* pHead2){
    if ( (pHead1 == NULL) && (pHead2 == NULL) )
        return NULL;
    if ( (pHead1 == NULL) || (pHead2 == NULL) )
        return (pHead1 == NULL)?pHead2:pHead1;
    ListNode* res;
    if ( pHead1->value < pHead2->value){
        res = pHead1;
        pHead1 = pHead1->next;
        res->next = Merge(pHead1,pHead2);
    }
    else{
        res = pHead2;
        pHead2 = pHead2->next;
        res->next = Merge(pHead1,pHead2);
    }
    return res;
}

发表于 2018-03-06 20:22:29 回复(0)

import java.util.LinkedList;
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if (list1 == null) {
            return list2;
        }
        if (list2 == null) {
            return list1;
        }
        ListNode head = new ListNode(-1);
        ListNode cur = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                cur.next = list1;
                list1 = list1.next;
            } else {
                cur.next = list2;
                list2 = list2.next;
            }
            cur = cur.next;
        }
        while (list1 != null) {
            cur.next = list1;
            list1 = list1.next;
        }
        while (list2 != null) {
            cur.next = list2;
            list2 = list2.next;
        }
        return head.next;
    }
}

发表于 2018-07-13 23:38:36 回复(0)
public ListNode Merge(ListNode list1, ListNode list2) {
        if(list1==null&&list2!=null)
            return list2;
        else if(list1!=null&&list2==null)
            return list1;
        else if(list1==null&&list2==null)
            return null;
        else{
            ListNode index = new ListNode(-1);
            ListNode index1=list1;
            ListNode index2=list2;
            ListNode tail=index;
            while(index1!=null&&index2!=null){
                if(index1.val<=index2.val){
                    tail.next=index1;
                    
                    index1=index1.next;
                }
                else{
                    tail.next=index2;
                    index2=index2.next;
                }
                tail=tail.next;
            }
            while(index1!=null){
                tail.next=index1;
                index1=index1.next;
            }
            while(index2!=null){
                tail.next=index2;
                index2=index2.next;
            }
            index=index.next;
            return index;    
        }
    }
怎么感觉我的好长!!!!
发表于 2017-10-20 20:35:17 回复(0)
import java.util.*;
public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1 == null && list2 == null)
			return null;
        ArrayList<Integer> list = new ArrayList<Integer>();
		ArrayList<ListNode> result = new ArrayList<ListNode>();
		while (list1 != null) {
			list.add(list1.val);
			list1 = list1.next;
		}
		while (list2 != null) {
			list.add(list2.val);
			list2 = list2.next;
		}
		Collections.sort(list);
		for(int i = 0;i<list.size();i++){
			ListNode temp = new ListNode(list.get(i));
			result.add(temp);
		}
		for(int i = 0;i<result.size()-1;i++){
			result.get(i).next = result.get(i+1);
		}
		return result.get(0);
    }
}

发表于 2016-06-29 18:06:49 回复(2)
感觉本题的答案大多是一次插入一个节点,如果遇到{2,3,4,7,8,9},{0,1,5,6,10,11}这样的两个链表,这种方法则显得很麻烦;在不开辟新空间的情况下,如果一次能插入一段节点,效率会大大提高,各位道友觉得呢?
编辑于 2015-10-14 14:40:23 回复(3)