力扣hot100 - 21、合并两个有序链表

题目：思路一：迭代
整体思路：如上例所示，

当 l1 和 l2 都不是空链表时，判断 l1 和 l2 哪一个链表的头节点的值更小，将较小值的节点添加到结果里，当一个节点被添加到结果里之后，将对应链表中的节点向后移一位

具体实现：我们需要拿一个哨兵节点dummy 来存储后面的有序的节点（还能便于最后返回结果，return dummy.next，不然返回结果很麻烦），然后用tail来维护合并后有序节点的尾部；不断l1和l2的大小，谁小tial就指向谁，同时小的一方后移；知道一方为null；最后tail指向不为空的一方。

时间复杂度O（m+n）空间复杂度O（1）

代码：

/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode mergeTwoLists(ListNode list1, ListNode list2) { ListNode dummy = new ListNode(); ListNode tail = dummy; while( list1 != null && list2 != null){ if(list1.val >= list2.val){ tail.next = list2; list2 = list2.next; }else{ tail.next = list1; list1 = list1.next; } tail = tail.next; } if( list1 != null){ tail.next = list1; } if(list2 != null){ tail.next = list2; } return dummy.next; } }