合并两个有序链表

链表概念:

• 是由一组节点组成的的集合，其中每个数据项都是一个节点的一部分，每个节点还包含指向下一个节点的链接。
• 链表是结构体最重要的应用， 它是一种非固定长度的数据结构，是一种动态存储技术， 它能够根据数据的结构特点和数量使用内存，尤其适用于数据个数可变的数据存储。

链表基本元素

• 1.节点：每个节点有两个部分，左边部分称为值域，用来存放用户数据；右边部分称为指针域，用来存放指向下一个元素的指针。
• 2.head:head节点永远指向第一个节点
• 3.tail: tail永远指向最后一个节点

• 4.None:链表中最后一个节点的指针域为None值

  
  image.png

头指针与头结点以及首元结点的关系:

image.png

题目

将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。

示例

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

思路一: 迭代

• 创建一个新的链表用来存储排列数据, 然后用while循环检测 l1和 l2中的val值,如果l1.var<=l2.var,那么就让新链表的next指针指向l1的val,,然后改变l1的指针指向并且将l1的下一个值指向l1,依次迭代,反之,如果l1.val>l2.var 那么就让新链表的next指针指向l2的val,,然后改变l2的指针指向并且将l2的下一个值指向l2,依次迭代,直到左右节点迭代完,判断l1是否为空,返回新链表l3.

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        // 头结点
        ListNode head;
        if (l1.val <= l2.val) {
            head = l1;
            l1 = l1.next;
        } else {
            head = l2;
            l2 = l2.next;
        }
        
        ListNode cur = head;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur = cur.next = l1;
                l1 = l1.next;
            } else {
                cur = cur.next = l2;
                l2 = l2.next;
            }
        }
        
        if (l1 == null) {
            cur.next = l2;
        } else if (l2 == null) {
            cur.next = l1;
        }
        return head;
        
    }
}

思路二 递归

public ListNode mergeTwoLists(ListNode k1, ListNode k2) {
        if (k1 == null) return k2;
        if (k2 == null) return k1;
        
        if (k1.val <= k2.val) {
            k1.next = mergeTwoLists(k1.next, k2);
            return k1;
        } else {
            k2.next = mergeTwoLists(k1, k2.next);
            return k2;
        }
    }