Question

Consider a linked list with n integers. Each node of the list is numbered from ‘1’ to ‘n’. Write an algorithm to split this list into 4 lists so that 

first list contains nodes numbered 1,5, 9, 13- - - 

second list contains nodes numbered 2, 6, 10, 14- - - 

third list contains nodes numbered 3, 7, 11, 15- - - 

and fourth list contains nodes numbered 4,8, 12, 16- - - 

Answer 1

Algorithm for the above said task is as follows: -

Let us denote the pointer to an item in the original linked list as P

Then the data and consequent pointers will be denoted as P->data and P->next respectively.

We assume that the functions list1.add (x), list2.add (x), list3.add (x) and list4.add (x) is defined to insert the “item x” into the linked list list1, list2, list3 and list4 respectively. 

start

set i = 1

while ( P->next != NULL )

Do

If (i % 4 = 1)

List1.add (P->data)

Else if (i % 4 = 2)

List2.add (P->data)

Else if (i % 4 = 3)

List3.add (P->data)

Else

List4.add (P->data) 

P = P->next //increment P to point to its next location i++ // increment i to count the next node in sequence. 

Done

End