题目：输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。
解法1：使用递归
代码：
package demo;
public class Test17 {
public static class ListNode {
int value;
ListNode next;
}
/**
* 递归
* @param head1
* @param head2
* @return
*/
public static ListNode merge(ListNode head1, ListNode head2) {
if(head1 == null) {
return head2;
} else if(head2 == null) {
return head1;
}
// 创建一个临时结点
ListNode tmp = null;
if(head1.value < head2.value) {
tmp = head1;
tmp.next = merge(head1.next, head2);
} else {
tmp = head2;
tmp.next = merge(head1, head2.next);
}
return tmp;
}
public static void printList(ListNode head) {
while(head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head1 = new ListNode();
head1.value = 1;
head1.next = new ListNode();
head1.next.value = 3;
head1.next.next = new ListNode();
head1.next.next.value = 4;
head1.next.next.next = new ListNode();
head1.next.next.next.value = 7;
ListNode head2 = new ListNode();
head2.value = 2;
head2.next = new ListNode();
head2.next.value = 4;
head2.next.next = new ListNode();
head2.next.next.value = 6;
head2.next.next.next = new ListNode();
head2.next.next.next.value = 8;
ListNode head = new ListNode();
head = merge(head1, head2);
printList(head);
}
}
运行结果
解法2：使用循环
代码如下：
package demo;
public class Test17 {
public static class ListNode {
int value;
ListNode next;
}
/**
* 使用循环
* @param head1
* @param head2
* @return
*/
public static ListNode merge(ListNode head1, ListNode head2) {
if(head1 == null) {
return head2;
} else if(head2 == null) {
return head1;
}
// 创建一个当前处理结点
ListNode curr = new ListNode();
// 创建一个临时结点，存放当前处理结点即合并后的头结点
ListNode tmp = curr;
while(head1 != null && head2 != null) {
if(head1.value < head2.value) {
curr.next = head1;
head1 = head1.next;
} else {
curr.next = head2;
head2 = head2.next;
}
curr = curr.next;
}
if(head1 != null) {
curr.next = head1;
}
if(head2 != null) {
curr.next = head2;
}
return tmp.next;
}
public static void printList(ListNode head) {
while(head != null) {
System.out.print(head.value + "->");
head = head.next;
}
System.out.println("null");
}
public static void main(String[] args) {
ListNode head1 = new ListNode();
head1.value = 1;
head1.next = new ListNode();
head1.next.value = 3;
head1.next.next = new ListNode();
head1.next.next.value = 4;
head1.next.next.next = new ListNode();
head1.next.next.next.value = 7;
ListNode head2 = new ListNode();
head2.value = 2;
head2.next = new ListNode();
head2.next.value = 4;
head2.next.next = new ListNode();
head2.next.next.value = 6;
head2.next.next.next = new ListNode();
head2.next.next.next.value = 8;
ListNode head = new ListNode();
head = merge(head1, head2);
printList(head);
}
}
