Spliting a singly linked list into two sub-lists from the middle node in one pass

This is a puzzle like problem for linked lists. We’ll use similar solution for our code in Finding The Half Of Linked List in Single Traversal. But we’ll add some spice to the code in order to convert solution to be applied to this problem.

Ok let’s have a look to our proposed solution.

1. When we get the middle node, we’ll backup the middle node into a temporary Node struct.
2. We’ll then assign NULL to middle node’s next pointer. At this point we’re set for first sub-list.
3. For the second sub-list we get our second sub-lists head from our backed up middle node’s next pointer. This pointer will be our second half’s head node.
4. After that second half will be ready and we’re all set!

#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(Node* start)
{
    for (Node* n = start; 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;
}

// returns the second half's head
Node* divide_list(Node* middle)
{
    // store middle node
    Node temp;
    // temp.val = middle->val; // we do NOT need this assignment!
    temp.next = middle->next;

    // mark end of first half
    middle->next = NULL; // we're finished for the first half after that instruction

    // we already stored second half's head node in temp node's next pointer
    // so we'll return it
    return temp.next;
}


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(head);
    Node* half = half_of_list();

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

    Node* second_half = divide_list(half);
    cout << "first half:" << endl;
    display(head); // this will print first half
    cout << "second half:" << endl;
    display(second_half); // this will print second half

    return 0;
}