Leetcode-每日一题【剑指 Offer 25. 合并两个排序的链表】

题目

输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。

示例1：

输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4

限制：

• 0 <= 链表长度 <= 1000

解题思路

1.题目要求我们合并两个链表并使新链表中的节点仍然是递增排序的。

2.首先我们设置一个虚拟头节点merge，让 temp 指向 merge 

然后比较l1和l2指向元素的大小将小的元素先入队，若相等时将l2指向的元素先入栈

 然后将指针指向被入队元素的下一个元素(此处的l2就指向了 1 的下一个元素 3)

  

 

 这时l2已经指向null 了，我们只需要将还没有入队的l1中的元素接在 temp 后面即可。

代码实现

class Solution {public ListNode mergeTwoLists(ListNode l1, ListNode l2) {ListNode merge = new ListNode(0);ListNode temp = merge;while(l1 != null && l2 != null ){if(l1.val < l2.val){temp.next = l1;l1 = l1.next;}else{temp.next = l2;l2 = l2.next;}temp = temp.next;}temp.next = l1 == null ? l2 : l1;return merge.next;}
}

测试结果