
文章链接
数据结构-链表-单向链表
面5笔5合并两个有序的链表,保证合并后的链表依然有序
对于合并两个有序链表,我们可以先定义一个新链表的头节点和一个临时引用,先进行比较,哪一个链表的首位数小就把那一个作为新链表的头节点。
随后,分别比较两个链表后面数据的大小,借用临时引用,把较小的一个接入新链表。
此时,若一个链表为空,那可将剩下链表这部分的数据直接链入新链表。
代码如下:
public static <T extends Comparable<T>> SingleLinkedList<T>.Node<T> mergrLinkedList(
SingleLinkedList<T>.Node<T> head1,SingleLinkedList<T>.Node<T> head2){
SingleLinkedList<T>.Node<T> newHead = null;//确定新链表的头节点
if(head1.data.compareTo(head2.data)<0){
newHead = head1;
head2 = head1.next;
}else {
newHead = head2;
head2 = head2.next;
}
//临时引用在新链表中从前往后去跑
SingleLinkedList<T>.Node<T> tmp = newHead;
while (head1!=null&&head2!=null){
if(head1.data.compareTo(head2.data)<0){
tmp.next = head1;
head1 = head1.next;
}else {
tmp.next = head2;
head2 = head2.next;
}
tmp = tmp.next;
}
if(head1 == null){
tmp.next = head2;
}
if(head2 == null){
tmp.next = head1;
}
return newHead;
}