LeetCode如何合并两个有序链表

一、LeetCode如何合并两个有序链表

LeetCode是一个在线编程网站，它提供了各种算法题目供用户练习，其中之一就是如何合并两个有序链表。

二、有序链表的概念

有序链表是指其元素按照一定的顺序排列的链表，它的每个节点都存储着一个元素，每个节点的元素值都比它后面的节点的元素值小，它的特点是插入和删除操作的时间复杂度都是O(1)。

三、LeetCode如何合并两个有序链表

LeetCode合并两个有序链表的算法主要采用迭代的方法，它的基本思想是：比较两个链表的头节点的值，将较小的节点作为新链表的头节点，然后将该节点的下一个节点作为新的头节点，重复上述操作，直到两个链表都遍历完毕，此时新生成的链表即为合并后的链表。

四、LeetCode合并两个有序链表的具体实现

1234567891011121314151617
/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let head = new ListNode(null);
    let p = head;
    while (l1 && l2) {
        if (l1.val < l2.val) {
            p.next = l1;
            l1 = l1.next;
        } else {
            p.next = l2;
            l2 = l2.next;
        }
        p = p.next;
    }
    p.next = l1 ? l1 : l2;
    return head.next;
};

以上是LeetCode合并两个有序链表的具体实现，首先定义一个头节点，然后用一个游标p指向头节点，比较两个链表的头节点，将较小的节点作为新链表的头节点，然后将该节点的下一个节点作为新的头节点，重复上述操作，直到两个链表都遍历完毕，此时新生成的链表即为合并后的链表，最后返回链表头节点即可。