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.
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两个单链表的表头地址是相同的
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2019-05-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读