0

need some help turning this single linked list into a circular linked list. I am completly lost on how to get the first node and link it to the last one

#include <iostream>
using namespace std;

struct node
{
	int  Item;
	node* Next;
}; // end struct

node* Head;

typedef node* ptrType;
//====================================================================
void insert_node(ptrType& Head, int value)
{
	ptrType Cur;
	ptrType Prev;
	ptrType NewPtr;
	bool inserted;

	NewPtr = new node;
	NewPtr -> Item = value;
	NewPtr -> Next = NULL;  // just to be on the safe side
		                           
	
	if (Head == NULL) 
		Head = NewPtr; // case 1
	// NewPtr -> Next remains NULL, since
	// this is the list's end
	else if (NewPtr -> Item <= Head -> Item)
	{   // case 2
		NewPtr -> Next = Head;
		Head = NewPtr;
	}
	else
	{ 
		Prev = Head;
		Cur = Head -> Next;
		inserted = false;

		while (Cur != NULL && !inserted)
		{
			if (NewPtr -> Item <= Cur -> Item)
			{  // case 3
				NewPtr -> Next = Cur;
				Prev -> Next = NewPtr;
				inserted = true;
			}
			else
			{
				Prev = Prev -> Next;
				Cur  = Cur -> Next;
			}
		}
		if (!inserted)
		{
			Prev -> Next = NewPtr; // case 4
		}
		// NewPtr -> Next remains NULL,
		// since this is the list's end
	}
}
//==================================================================
void print_circle(ptrType Head)
{
	ptrType current = Head;

	if(Head == NULL)
		cout << "empty list\n";
	else
	{
		while(current != NULL)
		{
			cout << current->Item << endl;
			current = current->Next;
		}
	}
}
//==================================================================
void send_Data()
{
	for (int n = 1;n<10;n++)
		insert_node(Head,n);
}

int main()
{
	send_Data();
	print_circle(Head);

	int g;
	cin >> g;
	return 0;
}
4
Contributors
3
Replies
4
Views
6 Years
Discussion Span
Last Post by raptr_dflo
0

You should add a pointer to the previous node, or keep a pointer to your first node and add that as your "Next" node on your last node.

0

And once your last node's Next pointer points back to Head, you have to maintain and deal with that.

As far as dealing with it, your print_circle() routine will never end as currently written (current will never become NULL).

As far as maintaining it, you need to address specific cases:
+ what should happen when you add the first node to an empty list?
+ what should happen when a new node is added to the front of the list?
+ what should happen when a new node is added to the end of the list?
+ (as long as the last node already points to Head, adding a new node in the middle of the list should work as currently implemented!)

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.