Split 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

Download   Run Code

Output:

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

Java

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

Download   Run Code

Output:

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

Java

Download   Run Code

Output:

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


 

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

 
1 Star2 Stars3 Stars4 Stars5 Stars (1 votes, average: 5.00 out of 5)

Loading...

Thanks for reading.

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂


Leave a Reply

avatar
  Subscribe  
Notify of