Please send questions to
st10@humboldt.edu .
//---------------------------------------------------------------------
// File: divide.cpp
// Name: Chip Dixon, modified by Sharon Tuttle
// last modified: 3-23-05
//
// Contract: divide: node* -> node*
//
// Purpose: divides a linked structure whose beginning is
// <head> into 2 separate sublists of roughly the same
// length; returns a pointer to the head of the second
// sublist.
//
// preconditions: <head> points to a linked list of at least 2 nodes
//
// postconditions:
// * <head> now points to a list of roughly the first half of its
// original nodes; (either half of the nodes, or the ceiling of the
// number of nodes divided by 2 if there are an odd number of nodes;
// * returns a pointer that points to the remainder of the original
// nodes (either half of the nodes, or the floor of the number of nodes
// divided by 2 if there is an odd number of nodes.
//
// Examples:
// Even number of elements:
// If you had a linked list of nodes with data:
// 3 6 2 9 1 5
// ...with myHead pointing to the node containing 3, then
// divide(myHead) would return a pointer to the node with 9,
// myHead now points to a list containing 3, 6, 2, and
// returned pointer points to a list containing 9, 1, 5.
//
// Odd number of elements:
// If you had a linked list of nodes with data:
// 3 6 2 9 1
// ...with myHead pointing to the node containing 3, then
// divide(myHead) would return a pointer to the node with 9,
// myHead now points to a list containing 3, 6, 2, and
// returned pointer points to a list containing 9, 1.
//
// Boundary case: 2 elements
// If you had a linked list of nodes with data:
// 3 6
// ...with myHead pointing to the node containing 3, then
// divide(myHead) would return a pointer to the node with 6,
// myHead now points to a list containing 3, and
// returned pointer points to a list containing 6.
//
// libraries/other functions used: node.h
//---------------------------------------------------------------------
#include <cassert>
#include "node.h"
using namespace std;
node* divide (node *head)
{
node *leading, *trailing;
assert(head != NULL);
assert(head->get_next() != NULL);
trailing = head;
leading = head->get_next();
leading = leading->get_next(); // list has at least 2 elements
// try to move leading pointer 2 steps for every one
// step you move the trailing pointer
while (leading != NULL)
{
leading = leading->get_next();
trailing = trailing->get_next();
if (leading != NULL)
{
leading = leading->get_next();
}
}
leading = trailing->get_next(); // starts the second half of the list
trailing->set_next(NULL); // ends the first part of the list
return leading;
}