Error in creating a linked list from another linked list?

Question

I'm creating a linked list from another linked list. But second linked list is not getting formed and there's a memory leak message on running the program.

Here's a section of the code that's troubling-

Node *rearrangeLinkedList(Node *head){

    printLinkedList(head);

    int lengthoflist = 0;

    Node *temp = head;

    while (temp!=NULL)
    {
        lengthoflist++;
        temp=temp->next;
    }   

    Node *secondList = NULL;

    // just a variable node to store the head of second linked list-
    Node *headOfSecondList = secondList;

    int count=1;

    while (count<=lengthoflist/2)
    {
        Node *temproary = new Node();
        temproary->data=head->data;
        temproary->next=NULL;
        secondList=temproary;
        secondList=secondList->next;
        head=head->next;
        count++;
    }

    printLinkedList(headOfSecondList);

}

printLinkedList() function is perfectly printing out the incoming list but not the second linked list.

Answer 1

If I have understood correctly the function tries to build a new list from the first half of nodes of an existed list.

If so then there is no need to calculate the number of nodes in the source list. This is inefficient.

You declared the function having the return type Node *.

Node *rearrangeLinkedList(Node *head );

but the function returns nothing.

Within the function the variable headOfSecondList is set once to nullptr and is never changed.

Node *secondList = NULL;
Node *headOfSecondList = secondList;

Within the while loop new nodes are not chained in a list. There is always changed the variable secondList and its data member next is always set to NULL. So there are numerous memory leaks.

while (count<=lengthoflist/2)
{
    Node *temproary = new Node();
    temproary->data=head->data;
    temproary->next=NULL;
    secondList=temproary;
    secondList=secondList->next;
    head=head->next;
    count++;
}

The function can be written the following way.

Node * rearrangeLinkedList( Node *head )
{
    Node *new_head = nullptr;
    Node **tail = &new_head;

    Node *first = head, *current = head;

    while ( current != nullptr && ( current = current->next ) != nullptr )
    {
        current = current->next;

        *tail = new Node();
        ( *tail )->data = first->data;
        ( *tail )->next = nullptr;

        first = first->next;
        tail = &( *tail )->next;
    }

    return new_head;
}

To demonstrate the approach without counting the number of nodes in the source list that as I already pointed out is inefficient here is a demonstrative program with a class template List.

#include <iostream>

template <typename T>
class List
{
private:
    struct Node
    {
        T data;
        Node *next;
    } *head = nullptr;

public:
    List() = default;
    ~List()
    {
        while ( head )
        {
            Node *current = head;
            head = head->next;
            delete current;
        }
    }

    List( const List<T> & ) = delete;
    List<T> & operator =( const List<T> & ) = delete;

    void push_front( const T &data )
    {
        head = new Node { data, head };
    }

    List<T> & extract_half( List<T> &list ) const
    {
        Node **tail = &list.head;

        while ( *tail ) tail = &( *tail )->next;

        Node *first = this->head, *current = this->head;

        while ( current != nullptr && ( current = current->next ) != nullptr )
        {
            current = current->next;
            *tail = new Node { first->data, nullptr };
            first = first->next;
            tail = &( *tail )->next;
        }

        return list;
    }

    friend std::ostream & operator <<( std::ostream &os, const List &list )
    {
        for ( Node *current = list.head; current; current = current->next )
        {
            os << current->data << " -> ";
        }

        return os << "null";
    }
};

int main() 
{
    List<int> list1;

    const int N = 10;

    for ( int i = N; i != 0; )
    {
        list1.push_front( --i );
    }

    std::cout << list1 << '\n';

    List<int> list2;

    list1.extract_half( list2 );

    std::cout << list1 << '\n';
    std::cout << list2 << '\n';

    return 0;
} 

The program output is

0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> null
0 -> 1 -> 2 -> 3 -> 4 -> null

Answer 2

After

Node *secondList = NULL;

Node *headOfSecondList = secondList;

you don't modify headOfSecondList any more. It will still be NULL when you call

printLinkedList(headOfSecondList); // => printLinkedList(NULL);

But you have another error in the copy-function:

while (count<=lengthoflist / 2)
{
    Node *temproary = new Node();
    temproary->data=head->data;  
    temproary->next=NULL;        
    secondList=temproary;         // assign secondList 
    secondList=secondList->next;  // secondList->next is temporary->next is NULL!!
    head=head->next;
    count++;
}

Here you create a bunch of nodes that all have a next of NULL. You do indeed leak memory here. secondList gets set to NULL at the end of each iteration and when temporary goes out of scope you don't have any pointers to the allocated memory left.

The following should work

// Build first node
Node *secondList = new Node();
secondList->data = head->data;
// advance by one
head = head->next;

// Now this points to the real head instead of NULL
Node *headOfSecondList = secondList;

int count=1;

while (count<=lengthoflist / 2 - 1 ) // -1 since we already handled the head above
{
    Node *temproary = new Node();  // new node
    temproary->data = head->data;  // set data
    temproary->next = NULL;        // we have no next yet
    secondList->next = temproary;  // append temporary to secondList
    secondList = secondList->next; //advance secondList
    head = head->next;             // advance head
    count++;
}

printLinkedList(headOfSecondList);

I have skipped some validation here, but I hope the basic concept is clearer now.