Splitting a Linked List

I’ll try to explain how to split a linked list and return second part to another list. Logic is, first pass the list and count items. After that pass list till half of count and after passes return the address of list. Let’s look codes;

node struct should look like;

1

typedef struct tagNode{
	int data;
	struct tagNode* pNext;
}Node;

I have AddItemToEnd function;

 

Node* AddItemToEnd(Node* pList, int data)
{
	Node* pTemp;
	Node* pNewItem = malloc(sizeof(Node));
	pNewItem->data = data;
	pNewItem->pNext = NULL;

	if (NULL == pList)
		return pNewItem; // If list is empty, return new item.
	pTemp = pList;
	while (NULL != pTemp->pNext)
		pTemp = pTemp->pNext; // Pass the list until the end.
	pTemp->pNext = pNewItem; // Add my new item to the end.

	return pList; // return list
}

Let me add four item like 1,2,3,4. You can imagine it as like this picture:

2

And my Split function;

 

Node* SplitList(Node* pList){
	Node* pTemp;
	int count=1;
	int i;


	pTemp = pList; // I don't want to change my original list, thats why I used temp.

	if (NULL == pList->pNext || NULL == pList){
		return pList; // If list is empty or has only one item, cannot split and return list back.
	}

	while (NULL != pList->pNext){
		count++; // Counts items on the list. When pList's pNext become NULL counting will stop.
		pList = pList->pNext;
	}


	for (i = 0; i < count / 2; i++) 		
            pTemp = pTemp->pNext;
	
	return pTemp;

}

I’ve tried to trace it with an image;

3Finally my print and main functions here;

 

void PrintList(Node* list){

	while (NULL != list){
		printf("Data: %d\n", list->data);
		list = list->pNext;
	}

}


int main(int argc, char** argv)
{
	Node* list = NULL;
	Node* Split;
	int i;

	for (i = 0; i < 4; i++)
		list = AddItemToEnd(list, i + 1);

	Split = SplitList(list);

	printf("*****Before Split*****\n");
	PrintList(list);
	printf("\n*****After Split*****\n");
	PrintList(Split);

	return EXIT_SUCCESS;
}

My output is like this:

4

Reklamlar

Bir Cevap Yazın

Aşağıya bilgilerinizi girin veya oturum açmak için bir simgeye tıklayın:

WordPress.com Logosu

WordPress.com hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Twitter resmi

Twitter hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Facebook fotoğrafı

Facebook hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Google+ fotoğrafı

Google+ hesabınızı kullanarak yorum yapıyorsunuz. Çıkış  Yap / Değiştir )

Connecting to %s