Split the nodes of the given linked list into front and back halves

Given a list, split it into two sublists — one for the front half, and one for the back half. If the number of elements is odd, the extra element should go in the front list.

 

For example, the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7, 11}.

 


 

Probably the simplest strategy is to compute the length of the list, then use a for loop to hop over the right number of nodes to find the last node of the front half, and then cut the list at that point.

 
C++ implementation –
 

Download   Run Code

Output:

Front List – 6 -> 3 -> 4 -> null
Back List – 8 -> 2 -> 9 -> null

 


 

Fast/Slow pointer strategy

There is a trick technique that uses two pointers to traverse the list. A “slow” pointer advances one nodes at a time, while the “fast” pointer goes two nodes at a time. When the fast pointer reaches the end, the slow pointer will be about half way. For either strategy, care is required to split the list at the right point.

 
C++ implementation –
 

Download   Run Code

Output:

Front List – 6 -> 3 -> 4 -> null
Back List – 8 -> 2 -> 9 -> null

 

Source:
http://cslibrary.stanford.edu/105/LinkedListProblems.pdf

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂