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.

- When we get the middle node, we’ll backup the middle node into a temporary Node struct.
- We’ll then assign NULL to middle node’s next pointer. At this point we’re set for first sub-list.
- 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.
- 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;
}

### Like this:

Like Loading...

*Related*