【LeetCode算法-21】Merge Two Sorted Lists
LeetCode第21题
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.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。Example:
Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4
翻译：
合并两个有序链表并返回一个新的链表，新链表必须由前两个链表拼接而成
思路：
把两个单链表的表头的值相互比较，较小的ListNode插入到新建的单链表中，然后更新表头，继续比较表头的值，原理和插入排序类似
步骤1：
l1：1->2->4
l2：1->3->4
l：
步骤2：
l1：1->2->4
l2：3->4
l：1->
步骤3：
l1：2->4
l2：3->4
l：1->1->
步骤4：
l1：4
l2：3->4
l：1->1->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) { ListNode temp = new ListNode(-1); ListNode l = temp; while(l1 != null && l2 != null){ if(l1.val > l2.val){ temp.next = l2; l2 = l2.next; }else{ temp.next = l1; l1 = l1.next; } temp = temp.next; } temp.next = (l1!=null)?l1:l2; return l.next; } }
最后返回l.next是因为l和temp两个单链表的表头地址是相同的
欢迎关注我的微信公众号：安卓圈
更多精彩
