Splitting the linked list into two halves

Given a single linked list, how do we split it into two halves.

For example the list 1->2->3->4 should be divided into 1->2 and 3->4

If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3.

This problem can be efficiently solved using fast pointer, slow pointer mechanism explained in this post.

In this approach, the fast pointer moves two steps at a time where as the slow pointer moves one step at a time. By the time the fast pointer reaches the end of the list, slow pointer will be pointing to the end node of the first half. So we need to iterate the list only once.

Here is the C++ implementation.

	#include <iostream>

	using namespace std;

	struct ListNode {
	int val;
	ListNode *next;
	ListNode(int x) : val(x), next(NULL) {}
	};

	ListNode * Add(ListNode *head, int d)
	{
	ListNode *temp = new ListNode(d);
	temp->next = head;
	return temp;
	}

	void Print(ListNode *head)
	{
	if( !head )
	{
	cout << "Empty" << endl;
	return;
	}
	while( head )
	{
	cout << head->val << " ";
	head = head->next;
	}
	cout << endl;
	}
	//first and second are reference parameters because they have to be modified
	void Split(ListNode* head, ListNode* &first, ListNode* &second)
	{
	first = NULL;
	second = NULL;
	//Trivial cases
	if( !head )
	{
	return;
	}

	first = head;
	ListNode* slow = head;
	ListNode* fast = head->next;

	while( fast )
	{
	if( fast->next )
	fast = fast->next->next;
	else
	break;
	slow = slow->next;
	}
	//slow points the end of the first half;
	second = slow->next;
	slow->next = NULL;//Need to set this to end first half
	}
	void TestCase1()
	{
	ListNode first, second;
	Split(NULL, first, second);
	Print(first);
	Print(second);
	}
	void TestCase2()
	{
	ListNode first, second;
	Split(new ListNode(1), first, second);
	Print(first);
	Print(second);
	}
	void TestCase3()
	{
	ListNode first, second;
	ListNode *head = NULL;
	head = Add(head,2);
	head = Add(head,1);
	Split(head, first, second);
	Print(first);
	Print(second);
	}
	void TestCase4()
	{
	ListNode first, second;
	ListNode *head = NULL;
	head = Add(head,3);
	head = Add(head,2);
	head = Add(head,1);
	Split(head, first, second);
	Print(first);
	Print(second);
	}
	void TestCase5()
	{
	ListNode first, second;
	ListNode *head = NULL;
	head = Add(head,4);
	head = Add(head,3);
	head = Add(head,2);
	head = Add(head,1);
	Split(head, first, second);
	Print(first);
	Print(second);
	}
	int main()
	{
	TestCase1();
	TestCase2();
	TestCase3();
	TestCase4();
	TestCase5();
	return 0;
	}

view raw FrontBackSplitLinkedList.cpp hosted with

by GitHub

Leave a Reply Cancel reply