CODEWITHSUNDEEP
c++singly-linked-list
Gabriel
Gabriel

Reputation: 13

Middle of a linked list bug

I write a function to print the middle of a singly linked list, but when the list length is odd, it is not printing it (does not print anything just blank space), and when the list length is even, it is printing the mid (sum of the node, which is correct).

I have the following code:

struct Node {
    int value;
    Node* next;
};
 
Node* head = NULL;

void insert_element2(int x);
void mid_list(Node* head);

int main() {

    insert_element2(1);
    insert_element2(2);
    insert_element2(3); //etc 


    mid_list(head);

    return 0;
}


void insert_element2(int x) {
    Node* temp1 = new Node();
    temp1->value = x;
    temp1->next = NULL;

    if (head == NULL) 
        head = temp1;
    else {
        Node* temp2 = head;
        while(temp2->next != NULL) {
            temp2 = temp2->next;
        }
        temp2->next = temp1;
    }
}


void mid_list(Node* head) {
    Node* temp1 = head;
    Node* temp2 =  head;

    while (temp1->next != NULL) {  **// When i change "temp->next" with "temp" is acting opposite(even/odd)**
        temp1 = temp1->next->next;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Upvotes: 0

Views: 56

Answers (3)

Suthiro
Suthiro

Reputation: 1300

If I understand right, you are looking for the middle node. The next snippet does the trick:

void mid_list(Node* head) 
{
    Node* temp1 = head;
    
    auto nodeCount = 0u;
    while (temp1->next != nullptr) // walk through nodes if exists
    {
        temp1 = temp1->next;
        ++nodeCount; //count valid nodes
    }

    temp1 = head; //reset the temp
    for (auto ii=0u; nodeCount / 2 > ii; ++ii ) // walk to the middle node from the head
    {
        temp1 = temp1->next;
    }
    if (nullptr != temp1) // sanity check
        std::cout << temp1->value;
}

For odd number of entries it is a true middle, for even it is either the node before (if you start counting from 0) or the node right after the "middle" index (if start from 1).

Upvotes: 0

Remy Lebeau
Remy Lebeau

Reputation: 598434

Let's step through the logic for your example of an odd-sized list:

  • Upon entry to mid_list(), head is the value=1 node, and temp1 and temp2 are set to head. Note that you are NOT checking head for NULL, so your code will fail if the list is empty, but that is not the case in this example.

  • On the 1st loop iteration, temp1->next is not NULL, so temp1 gets set to temp1->next->next which is the value=3 node, and temp2 gets set to temp2->next which is the value=2 node.

  • On the 2nd loop iteration, temp1->next is NULL, so the loop breaks, and the value=2 node gets printed (not a blank space, like you claim). So far, so good.

Live Demo

Now, let's step through the logic for an even-sized list:

  • Upon entry to mid_list(), head is the value=1 node, and temp1 and temp2 are set to head.

  • On the 1st loop iteration, temp1->next is not NULL, so temp1 gets set to temp1->next->next which is the value=3 node, and temp2 gets set to temp2->next which is the value=2 node.

  • On the 2nd loop iteration, temp1->next is not NULL, so temp1 gets set to temp1->next->next which is NULL, and temp2 gets set to temp2->next which is the value=3 node.

  • On the 3rd loop iteration, temp1 is NULL so accessing temp1->next is undefined behavior and the code fails.

So, to fix this, you need to change your loop to something more like this instead:

void mid_list(Node* head)
{
    if (head == NULL) return;

    Node* temp1 = head;
    Node* temp2 = head;

    while (temp1->next != NULL) {
        temp1 = temp1->next->next;
        if (temp1 == NULL) break;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Live Demo

Or:

void mid_list(Node* head)
{
    if (head == NULL) return;

    Node* temp1 = head;
    Node* temp2 = head;

    while ((temp1 != NULL) && (temp1->next != NULL)) {
        temp1 = temp1->next->next;
        temp2 = temp2->next;
    }

    cout << temp2->value;
}

Live Demo

Depending on which "middle" node you are actually interested in when iterating an even-sized list - the node to the left or the right of the mid-point.

Upvotes: 2

shaista ambreen
shaista ambreen

Reputation: 46

There is one bug in your code, in while condition you must check "temp1->next" as you are pointing to its next inside the loop ,in case temp->next is NULL then temp1->next->next will be undefined.The code below will work fine:

    void mid_list(Node* head) {
    Node* temp1 = head;
    Node* temp2 =  head;

    while (temp1!=NULL && temp1->next != NULL) {  // here I have modified this line.
       temp1 = temp1->next->next;
       temp2 = temp2->next;
    }

    cout << temp2->value;
    }

Upvotes: 0

Related Questions