LeetCode第21题

• 2019 年 10 月 7 日
• 筆記

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两个单链表的表头地址是相同的