首页 > 代码库 > LeetCode | #21 Merge Two Sorted Lists
LeetCode | #21 Merge Two Sorted Lists
题目：
Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.
思路：
- 设置两个头指针，一个指针不动，用来返回最后头结点，一个指针用来组织节点顺序，遍历两链表，每次都指向小的节点
public class MergeTwoSortedLists {
public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode h1 = new ListNode(0), h2 = h1;
while(l1!=null && l2!=null){
if(l1.val < l2.val){
h1.next = l1;
l1 = l1.next;
}else{
h1.next = l2;
l2 = l2.next;
}
h1 = h1.next;
}
if(l1 == null){
h1.next = l2;
}
if(l2 == null){
h1.next = l1;
}
return h2.next;
}
}- 还有一种更屌的方法，递归，也是每次选出最小的节点，不过代码更加简洁
//递归解法，头指针每次指向两个列表中最小的节点，然后递归
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null)
return l2;
if(l2 == null)
return l1;
ListNode h;
if(l1.val < l2.val){
h = l1;
h.next = mergeTwoLists(l1.next, l2);
}else{
h = l2;
h.next = mergeTwoLists(l1, l2.next);
}
return h;
}LeetCode | #21 Merge Two Sorted Lists
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。