We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Merge two sorted linked lists
  2. Discussions

Merge two sorted linked lists

Sort by

recency

|

218 Discussions

|

  • wasifk308
     + 0 comments

    SinglyLinkedListNode* mergeLists(SinglyLinkedListNode* head1, SinglyLinkedListNode* head2) {

    if(head1 ==nullptr) { return head2; }

    if(head2 == nullptr) { return head1; }

    stack temp; while (head1 != nullptr && head2 != nullptr ) {

    if(head1->data <= head2->data)
{

   temp.push(head1->data );
   head1 = head1->next;

}else {
   temp.push(head2->data );
   head2 = head2->next;

}

    }

    while (head1 != nullptr) { temp.push(head1->data );

            head1 = head1->next;

    }

    while (head2 != nullptr) { temp.push(head2->data );

    head2 = head2->next;

    }

    SinglyLinkedListNode* res = nullptr;

    while(!temp.empty()){

    int tp = temp.top();

temp.pop();

    SinglyLinkedListNode *temp = new SinglyLinkedListNode(tp); temp->next = res; res = temp; }

    return res;

    }

  • anw_g01
     + 0 comments

    Using a dummy (temporary) node is neat trick to bypass head pointer management. Just don't forget to skip it when finished by returning head.next:

    def mergeLists(head1, head2):
    # if one LL is empty, return the other
    if head1 is None:
        return head2
    if head2 is None:
        return head1
    new = SinglyLinkedList()        # instantiate a new LL 
    curr = SinglyLinkedListNode(0)  # create dummy node
    new.head = curr                 # start pointer at dummy node
    # traverse both LLs:        
    curr1, curr2 = head1, head2     # pointers for each head
    while True:
        if curr1.data < curr2.data:
            curr.next = curr1
            curr1 = curr1.next
        else:
            curr.next = curr2
            curr2 = curr2.next
        curr = curr.next    # move to next node
        if curr1 is None or curr2 is None:
            break
    # attach the remaining LL:
    if curr1 is not None:
        curr.next = curr1
    if curr2 is not None:
        curr.next = curr2
    return new.head.next    # skip the dummy node

  • jorgepintomende1
     + 0 comments

    started with recursive then want to cry :(

    function mergeLists(head1, head2) {

    const elem = []
const res = (node, node2) => {
    let elem = node2 ? (node.data > node2.data ? node2 :node): node
    let nElem = node2 ? (node.data <= node2.data ? node2 :node): null
    return {
        data: elem.data,
        next: elem.next ? res(elem.next, nElem): nElem? res(nElem, null):null
    }
};
return res(head1,head2)

    }

  • vuhuutuan0
     + 0 comments

    My answer with Typescrit,

    Cause no starting code, i was do it for my self

    Questiom sample explain is wrong, it confusing me for a while.

    function main() {
    const ws: WriteStream = createWriteStream(process.env['OUTPUT_PATH']);
    const t: number = parseInt(readLine().trim(), 10);

    for (let i = 0; i < t; i++) {
        const n: number = parseInt(readLine().trim(), 10);
        const ns: number[] = []
        for (let j = 0; j < n; j++) ns.push(parseInt(readLine().trim(), 10))

        const m: number = parseInt(readLine().trim(), 10);
        const ms: number[] = []
        for (let j = 0; j < m; j++) ms.push(parseInt(readLine().trim(), 10))

        ws.write([...ns, ...ms].sort((a, b) => a - b).join(' ') + '\n');
    }

    ws.end();
}

  • cbisaccia78
     + 0 comments
    def mergeLists(head1, head2):
    ptr = ret = opposite = None
    if head1.data < head2.data:
        ptr = head1
        ret = head1
        opposite = head2
    else:
        ptr = head2
        ret = head2
        opposite = head1
    
    while ptr:
        while ptr.next and ptr.next.data < opposite.data:
            ptr = ptr.next
        
        next_p = ptr.next
        ptr.next = opposite
        ptr = opposite
        opposite = next_p

        if opposite is None:
            return ret