Merge Two Lists
出处
Given two sorted linked lists, write a function to merge these two lists, and return a new list which is sorted.
Solution
遇到同时处理两个链表的问题,循环的条件一般可以用 while( list1 && list2 ),当循环跳出后,再处理剩下非空的链表。这相当于:边界情况特殊处理,常规情况常规处理。
这是一个典型的需要同时处理两个链表的问题,可以先处理常规情况(两个链表都有剩下节点),再处理边界情况(其中一个链表已经遍历完毕)。在处理常规情况的时候,我们将当前两个链表中较小的那个节点放入新的链表。
Complexity
时间复杂度 O(n)
Code
Node mergeList(Node head1, Node head2){
if (head1 == null && head2 == null) return false;
if (head1 == null) return head2;
if (head2 == null) return head1;
Node dummy = new Node(-1);
Node backup = dummy;
while(head1 != null && head2 != null){
if (head1.value < head2.value){
dummy.next = head1;
head1 = head1.next;
} else {
dummy.next = head2;
head2 = head2.next;
}
dummy = dummy.next;
}
if (head1 != null){
dummy.next = head1;
} else {
dummy.next = head2;
}
return backup.next;
}