Merge Two Sorted Linked Lists

I solved this problem in C++. I was having trouble though understanding what return headA; and return headB; returns after going back down the recursion tree. A code review is also appreciated!

You’re given the pointer to the head nodes of two sorted linked lists. The data in both lists will be sorted in ascending order. Change the next pointers to obtain a single, merged linked list which also has data in ascending order. Either head pointer given may be null meaning that the corresponding list is empty.

/*   Merge two sorted lists A and B as one linked list   Node is defined as    struct Node   {      int data;      struct Node *next;   } */ #include <iomanip>  Node* MergeLists(Node *headA, Node* headB) {     // check if either linked list is empty, then return the other one. when doing recursive, a new headA and headB will be passed in, so it will add the entire list correctly   if (headA == NULL) {       return headB;   } else if (headB == NULL) {       return headA;   } else { // if neither empty go into this block       if (headA->data <= headB->data) {           headA->next = MergeLists(headA->next, headB);           // returns the entire linked list after the recursion parses it in the correct order           // not too sure what is returned going down the recursion tree           // headA = 1 -> 3 -> 5 -> 6 -> NULL           // headB = 2 -> 4 -> 7 -> NULL           // would it return 6, 5, 3, 1, 1->2->3->4->5->6->7 after recursion tree?           return headA;       } else {           headB->next = MergeLists(headA, headB->next);           // return 7, 4, 2 after recursion tree?           return headB;       }   } } 

Replay

An iterative algorithm

Of course, you can do the job recursively. However, if you merge large lists that way, there is a chance of running out the stack space. Also, the space complexity of your recursive method is \$\Theta(n)\$ (on the stack). Using iteration, you can reduce the space complexity to \$\Theta(1)\$, and that is how:

Node* MergeLists(Node *headA, Node* headB)
{
    if (!headA)
    {
        return headB;
    }

    if (!headB)
    {
        return headA;
    }

    Node* head;
    Node* tail;

    if (headA->data < headB->data)
    {
        head = headA;
        tail = headA;
        headA = headA->next;
    }
    else
    {
        head = headB;
        tail = headB;
        headB = headB->next;
    }

    while (headA && headB)
    {
        if (headA->data < headB->data)
        {
            tail->next = headA;
            tail = headA;
            headA = headA->next;
        }
        else
        {
            tail->next = headB;
            tail = headB;
            headB = headB->next;
        }
    }

    while (headA)
    {
        tail->next = headA;
        tail = headA;
        headA = headA->next;
    }

    while (headB)
    {
        tail->next = headB;
        tail = headB;
        headB = headB->next;
    }

    return head;
}

Coding conventions

You use a consistent coding style what comes to spacing, braces, etc. However, I suggest you don't use more than 80 characters on any line; for example:

// check if either linked list is empty, then return the other one. when doing recursive, a new headA and headB will be passed in, so it will add the entire list correctly

Why not split it in more than one line:

// check if either linked list is empty, then return the other one.
// when doing recursive, a new headA and headB will be passed in,
// so it will add the entire list correctly

Hope that helps.

Your solution is fine, subject to the caveat that the use of recursion imposes a limit on the length of your lists, due to the possibility of stack overflow.

Your comments betray a sense of insecurity about how it works, though. Just consider what happens locally, and trust that recursion will take care of the rest.

I also suggest un-nesting the else block.

/**
 * Recursively merge two sorted lists by manipulating node pointers.
 * Returns the head of the merged list.
 */
Node* MergeLists(Node *headA, Node* headB)
{
    if (headA == NULL) {
        return headB;
    } else if (headB == NULL) {
        return headA;
    } else if (headA->data <= headB->data) {
        headA->next = MergeLists(headA->next, headB);
        return headA;
    } else {
        headB->next = MergeLists(headA, headB->next);
        return headB;
    }
}

Category: c# Time: 2016-07-28 Views: 0

Related post

iOS development

Android development

Python development

JAVA development

Development language

PHP development

Ruby development

search

Front-end development

Database

development tools

Open Platform

Javascript development

.NET development

cloud computing

server

Copyright (C) avrocks.com, All Rights Reserved.

processed in 0.272 (s). 12 q(s)