Finding The Half Of Linked List in Single Traversal

This is like a puzzle question: you iterate the list but at the end of the iteration (i.e. when you reach the end of linked list) you should display the half. The question seams hard because you do not know how many node exist in the list. So, how you find the half when you reach at the tail. One solution may be to store all elements into an array, but this is quite inefficient and possibly infeasible way to solve this question.

My proposed solution is:

• Traverse the list with double next, this is iterating the list with node->next->next
• Hold another pointer for half of the list. While iterating double next half of the list pointer iterates with one next.

I added the code for a simple list (supports addition to head, and tail – I did not test the tail :).

Code below shows the half of the list:

#include <iostream>

using namespace std;

struct Node {
    int val;
    struct Node* next;
};

Node* head;

void add_node_head(int val)
{
    Node* n = new Node;
    n->val = val;

    if (head == NULL) {
        head = n;
        n->next = NULL;
    }
    else {
        n->next = head;
        head = n;
    }
}

void add_node_tail(int val)
{
    Node* node = new Node;
    node->val = val;
    node->next = NULL;

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

        n-> next = node;
    }
}

void display()
{
    for (Node* n = head; n != NULL; n = n->next) {
        cout << n->val << endl;
    }
}

Node* half_of_list()
{
    Node* n = head;
    Node* half = head;;
    while (n) {
        if (n->next) {
            n = n->next->next;
            half = half->next;
        }
        else
            break;
    }

    return half;
}


int main() {

    add_node_head(10);
    add_node_head(20);
    add_node_head(30);
    add_node_head(40);
    add_node_head(50);
    add_node_head(60);
    add_node_head(70);

    display();
    Node* half = half_of_list();

    cout << "half: " << half->val << endl;

    return 0;
}