链表操作

题目链接-来源：力扣（LeetCode）

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

示例1：

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

思路：

基本的链表操作，也是归并排序操作的主体部分（两个链表代表的子序列已经排序完成）。
主体部分用两个指针 cur1 cur2 分别记录两个链表当前访问的位置，比较大小，依次复制即可。最后分别对剩余部分一次性复制处理。
链表操作前增加一个无意义的头结点 newHead ，可以事半功倍，免去繁琐的空链表判断。事后返回 newHead.next 即可。

时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode l = new ListNode(0), cur = l;
        
        ListNode curL1 = l1, curL2 = l2;
        while (curL1 != null && curL2 != null) {
            if (curL1.val <= curL2.val) {
                cur.next = curL1;
                curL1 = curL1.next;
            } else {
                cur.next = curL2;
                curL2 = curL2.next;
            }
            cur = cur.next;
        }
        
        if (curL1 == null) {
            cur.next = curL2;
        } else {
            cur.next = curL1;
        }
        
        return l.next;
    }
}