合并两个有序的单链表，合并之后的链表依然有序【出现频率高】
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了合并两个有序的单链表，合并之后的链表依然有序【出现频率高】，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1588字，纯文字阅读大概需要3分钟。
内容图文
合并两个有序的单链表，合并之后的链表依然有序： 这道题经常被各公司考察。 例如： 链表1：
1->2->3->4 链表2：
2->3->4->5
合并后：
1->2->2->3->3->4->4->5
解题思路：
挨着比较链表1和链表2。
这个类似于归并排序。尤其要注意两个链表都为空、和其中一个为空的情况。只需要O (1) 的空间。时间复杂度为O (max(len1,len2))
public
Node mergeLinkList(Node head1, Node head2) {
if (head1 == null && head2 == null) {
// 如果两个链表都为空 return null; }
if (head1 == null) {
return head2;
}
if (head2 == null) {
return head1;
}
Node head; // 新链表的头结点
Node current; // current结点指向新链表
// 一开始，我们让current结点指向head1和head2中较小的数据，得到head结点if (head1.data < head2.data) {
head = head1;
current = head1;
head1 = head1.next;
} else {
head = head2;
current = head2;
head2 = head2.next;
}
while (head1 != null && head2 != null) {
if (head1.data < head2.data) {
current.next = head1;
// 新链表中，current指针的下一个结点对应较小的那个数据
current = current.next; // current指针下移
head1 = head1.next;
} else {
current.next = head2;
current = current.next;
head2 = head2.next;
}
}
// 合并剩余的元素if (head1 != null) {
// 说明链表2遍历完了，是空的
current.next = head1;
}
if (head2 != null) {
// 说明链表1遍历完了，是空的
current.next = head2;
}
return head;
}
测试代码
public
static
void
main(String[] args) {
LinkList list1 = new LinkList();
LinkList list2 = new LinkList();
// 向LinkList中添加数据for (int i = 0; i < 4; i++) {
list1.add(i);
}
for (int i = 3; i < 8; i++) {
list2.add(i);
}
LinkList list3 = new LinkList();
list3.head = list3.mergeLinkList(list1.head, list2.head); // 将list1和list2合并，存放到list3中
list3.print(list3.head);// 从head节点开始遍历输出
}
测试结果：
0
1
2
3
3
4
5
6
7
原文：http://www.cnblogs.com/guweiwei/p/6855626.html
内容总结
以上是互联网集市为您收集整理的合并两个有序的单链表，合并之后的链表依然有序【出现频率高】全部内容，希望文章能够帮你解决合并两个有序的单链表，合并之后的链表依然有序【出现频率高】所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。