1. Problem description

• The design algorithm decomposes the single chain table L1 of a leading node into two chain tables L2 and L3 with the same structure, in which the node of L2 table is the node whose median value is less than zero in L1 table, and the node of L3 table is the node whose median value is greater than zero in L1 table (the element in L1 is non-zero integer, so L2 and L3 tables are required to use the node of L1 table).

2. Topic analysis

• The head node of the L2 table uses the head node of the original L1 table to apply for a new head node for the L3 table. Starting from the first node of L1 table, take each node p in turn, and judge whether the value of node p is less than 0. Using the forward interpolation method, insert the node less than 0 into L1 table, and the node greater than or equal to 0 into L3 table.

// Linked list decomposition
void DisCompose(LinkList &L1, LinkList &L2, LinkList &L3)
{
	LNode *p;
	p = L1->next;      // p is the working pointer
	
	L2 = L1;
	L2->next = NULL;   // L2 table initialization
			
	L3 = new LNode;   // Apply node space for L3
	L3->next = NULL;    // L3 initialized to empty table
		
	while (p != NULL)
	{
		LNode *r;
		r = p->next;      // The successor of temporary p
		if (p->data < 0)
		{
			p->next = L2->next; 
			L2->next = p;       // Link nodes less than 0 into L2 table, forward interpolation
		}     
		else if (p->data > 0)
		{ 
			p->next = L3->next; 
			L3->next = p; 
		}           // Chain nodes greater than or equal to 0 into table C, forward interpolation
				
		p = r;   // p points to a new pending node
	}
}

3. Code implementation

• main.cpp

#include <iostream>

using namespace std;

typedef struct LNode
{
	int data;
	struct LNode *next;
}LNode, *LinkList;

int InitList(LinkList &L)
{
	L = new LNode;
	L->next = NULL;
	return 1;
}

void TraveList(LinkList L)
{
	LNode *p;
	p = L->next;

	while (p)
	{
		printf("%d ", p->data);
		p = p->next;
	}
	printf("\n");
}

// Establishing chain list by tail insertion
void CreateList(LinkList &L, int n)
{
	L = new LNode;
	L->next = NULL;
	LNode *r;
	r = L;
	for (int i = 0; i < n; i++)
	{
		printf("Please enter the link list No.%d Values of elements:", i + 1);
		LNode *s;
		s = new LNode;
		scanf("%d", &s->data);
		s->next = NULL;
		r->next = s;
		r = s;
	}
}

// Linked list decomposition
void DisCompose(LinkList &L1, LinkList &L2, LinkList &L3)
{
	LNode *p;
	p = L1->next;      // p is the working pointer
	
	L2 = L1;
	L2->next = NULL;   // L2 table initialization
			
	L3 = new LNode;   // Apply node space for L3
	L3->next = NULL;    // L3 initialized to empty table
		
	while (p != NULL)
	{
		LNode *r;
		r = p->next;      // The successor of temporary p
		if (p->data < 0)
		{
			p->next = L2->next; 
			L2->next = p;       // Link nodes less than 0 into L2 table, forward interpolation
		}     
		else if (p->data > 0)
		{ 
			p->next = L3->next; 
			L3->next = p; 
		}           // Chain nodes greater than or equal to 0 into table C, forward interpolation
				
		p = r;   // p points to a new pending node
	}
}
	
int main()
{
	LinkList L1, L2, L3;

	if (InitList(L1))
	{
		printf("L1 Initialization successful!\n");
	}
	else
	{
		printf("L1 initialization failed!\n");
	}

	printf("Please input L1 Length:");
	int n1;
	scanf("%d", &n1);
	CreateList(L1, n1);
	TraveList(L1);

	DisCompose(L1, L2, L3);
	printf("The list is broken down into L2,L3:\n");
	printf("L2: ");
	TraveList(L2);
	printf("L3: ");
	TraveList(L3);

	system("pause");

	return 0;
}

• Operation result