题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
分析
1.递归
public static ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
if (list1.val < list2.val) {
list1.next = Merge(list1.next, list2);
return list1;
} else {
list2.next = Merge(list1, list2.next);
return list2;
}
}
2.非递归：注意保存第一个节点作为返回结果
public static ListNode Merge(ListNode list1, ListNode list2) {
if (list1 == null) return list2;
if (list2 == null) return list1;
ListNode currentNode = null;
ListNode result = null;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
if (currentNode == null) {
currentNode = list1;
result = currentNode;
} else {
currentNode.next = list1;
currentNode = currentNode.next;
}
list1 = list1.next;
} else {
if (currentNode == null) {
currentNode = list2;
result = currentNode;
} else {
currentNode.next = list2;
currentNode = currentNode.next;
}
list2 = list2.next;
}
}
if (list1 == null) {
currentNode.next = list2;
}
if (list2 == null) {
currentNode.next = list1;
}
return result;
}
