Given a linked list of numbers, it will shue the rst half of the list with the second half of the list so that the nodes will be listed from each...

Given a linked list of numbers, it will shue the rst half of the list with the second half

of the list so that the nodes will be listed from each half alternatively. For example, in the

singly linked list case, if the list is:

Head ->[ 2 ]->[ 3 ]->[ 1 ]->[ 6 ]->[ 8 ]->[ 5 ]->[ 7 ]->[ 13 ]->[ 0 ]->nil

then the resulting list, after the operation, is:

Head ->[ 2 ]->[ 5 ]->[ 3 ]->[ 7 ]->[ 1 ]->[ 13 ]->[ 6 ]->[ 0 ]->[ 8 ]->nil

Note that when the number of elements in the list is odd, say n = 2k+1, the rst half consists

the rst k + 1 elements and the second consists of the remaining k elements.

To present your results, you may print the list in the following form to the screen:

***** Before the operation *****

** first half **

2, 3, 1, 6,

8

** second half **

5, 7, 13, 0

***** After the shuffle operation *****

** the list **

2, 5, 3, 7,

1, 13, 6, 0,

8