输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4
限制：0 <= 链表长度 <= 1000
1. 循环法
一个元素一个元素比较，比较后按照大小结果判断下一个比较
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//保存新和并排序好的链表（头结点）
ListNode resultNode = new ListNode();
//尾节点来增加数据
ListNode tail = resultNode;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
tail.next = l1;
l1 = l1.next;
tail = tail.next;
}else{
tail.next = l2;
l2 = l2.next;
tail = tail.next;
}
}
if(l1 == null){
tail.next = l2;
}
if(l2 == null){
tail.next = l1;
}
//最终返回的是头节点的下一个节点开始的链表,因为最初的头节点不是我们需要合并的数据
return resultNode.next;
}
}
2. 递归法
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null){
return l2;
}
if(l2 == null){
return l1;
}
if(l1.val > l2.val){
l2.next = mergeTwoLists(l1,l2.next);
return l2;
}else{
l1.next = mergeTwoLists(l1.next,l2);
return l1;
}
}
}
这样写可能会比较好理解一些
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode();
//递归出口1,当一直往下面比较的时候，如果出现其中一个已经没有元素了，那么直接将剩下的链表接到排序好的链表的后面
if(l1 == null){
return l2;
}
//递归出口2
if(l2 == null){
return l1;
}
if(l1.val > l2.val){
head = l2;
head.next = mergeTwoLists(l1,l2.next);
}else{
head = l1;
head.next = mergeTwoLists(l1.next,l2);
}
return head;
}
}
下面这张图可以帮助你理解递归
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名,转载请标明出处
最后编辑时间为:
2021/05/17 00:17