面试之路(29)-合并两个排序的链表(递归和非递归)

2016-11-09 16:26:24来源:oschina作者:fengsehng人点击

第七城市
链表的类:
class ListNode{
int key;
ListNode next;
}
思路: 这个和数组不一样,不需要采用双指针,从后往前来代码:
递归
public ListNode merge(ListNode head1,ListNode head2){
if(head1 == null){
return head2;
}else if(head2 == null){
return head1;
}
ListNode node = null;
if(head1.key < head2.key){
node =head1;
node.next = merge(head1.next,head2);
}else{
node = head2;
node.next = merge(head1,head2.next);
}
return node;
}
非递归
public ListNode merge(ListNode head1,ListNode head2){
if(head1 == null){
return head2;
}else if(head2 == null){
return head1;
}
ListNode node = null;
if(head1.key < head2.key){
node = head1;
head1 = head1.next;
}else{
node = head2;
head2 = head2.next;
}
ListNode current = node;
while(head1 != null && head2 != null){
if(head1.key < head2.key){
node.next = head1;
head1 = head1.next;
node = node.next;
}else{
node.next = head2;
head2 = head2.next;
node = node.next;
}
}
if(head1 == null){
node.next = head2;
}
if(head2 == null){
node.next = head1;
}
return current;;
}
第七城市

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台