算法(十六)：合并两个排序的链表

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了算法(十六)：合并两个排序的链表，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1878字，纯文字阅读大概需要3分钟。

内容图文

题目描述

       输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

题目分析

1. 使用递归的思想：将两个链表的节点按大小循环插入。
2. 使用选择排序的思想：因为两个链表都是有序的，每次取第二个链表的第一个节点(这样每次第二个链表的第一个节点都是第二个链表中最小的)，将这个节点插入到到第一个链表中，如果某次插入的位置是第一个链表的末尾，则直接将第一个链表和第二个链表剩余的部分相连。要注意的是第一次比较时要单独比较，因为第一个链表的头节点可能会改变，之后每次比较都从第一次插入的节点开始，因为第二个链表的剩余部分的值都大于该节点的值。

Java实现

1. 递归

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

2. 使用选择排序思想

	public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode current1 = list1;
        ListNode current2 = list2;
        ListNode temp1 = null;//用于临时存储下一个节点
        ListNode temp2 = list1;//用于存储插入的位置，便于下一次插入时从该位置开始比较
        boolean isRight = false;//设置标记，用于判断该次插入的位置是不是第一个链表的末尾
        while(current2 != null){
            temp1 = current2.next;//用于储存下一个节点
            for(current1 = temp2;current1 != null;current1 = current1.next){
                isRight = false;
                if(current2 == list2 && current2.val < current1.val){//取出的节点为原链表头结点并且第一个链表的头结点大于第二个链表的头结点时
                    current2.next = current1;
                    list1 = current2;
                    temp2 = list1;
                    break;
                }else{
                    if(current1.next == null){//当插入的位置为末尾时，直接将两个链表连接
                        current1.next = current2;
                        isRight = true;
                        break;
                    }else if(current2.val < current1.next.val){//找到插入位置并且插入的位置不是末尾
                        current2.next = current1.next;
                        current1.next = current2;
                        temp2 = current2;
                        break;
                    }
                }
            }
            if(isRight){//如果某次插入的位置为第一个链表的末尾，结束
                break;
            }
            current2 = temp1;//取出下一个节点
        }
        return list1;
    }

内容总结

以上是互联网集市为您收集整理的算法(十六)：合并两个排序的链表全部内容，希望文章能够帮你解决算法(十六)：合并两个排序的链表所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---