LinkList:Folding a LinkList

Input : LinkList(Even Number of  Nodes)

Output : Folded Link List

Input : LinkList(Odd Number of  Nodes)

Output : Folded Link List

Solution:

We begin with a recursive algorithm to solve the problem. The function FoldLinkList will take input as head of list and return the head after connect First node( 1 ) to LastNode ( 6 ) and again the FoldLinkList is called on Nodes 2 .Function LastNode will return the last Element of current linklist and set the previous node of last node to null;


Code:
Class to represent Node in a LinkList