all articles

leetcode war 21 - Merge Two Sorted Lists

2017-10-10 @sunderls

leetCode js

https://leetcode.com/problems/merge-two-sorted-lists/description/

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

analysis

this seems fairly easy, just use two cursors and merge them.

let result, p1, p2

while p1 && p2:
    if p1.val <= p2:
        result.next = p1
        p1 = p1.next
    else:
        result.next = p2
        p2 = p2.next

    result = result.next

// after one is done
if p1
    result.next = p1

if p2
    result.next = p2

trial - use two cursor to merge the list

/**
 * 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) {
    var p1 = l1;
    var p2 = l2;
    var head = p3 = new ListNode();

    while (p1 && p2) {
        if (p1.val <= p2.val) {
            p3.next = p1;
            p1 = p1.next;
        } else {
            p3.next = p2;
            p2 = p2.next;
        }

        p3 = p3.next;
    }

    if (p1) {
        p3.next = p1;
    }

    if (p2) {
        p3.next = p2;
    }

    return head.next;
};

it passed and ranks top 10%. not bad