September 11, 2010

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. So FrontBackSplit() on the list {2, 3, 5, 7, 11} should yield the two lists {2, 3, 5} and {7, 11}.

This is a very good linked list question, as there are tricky cases you have to consider, and getting them all right in one place is harder than it looks. It also has a very obvious simple solution, which is to iterate the list twice. The first time to count how many elements in the list, and the second time to find the splitting point.

Can we do better? You bet.

Hint: Try to use two pointers to traverse the list.

Solution: We use two pointers (we call it a slow pointer and a fast pointer). The slow pointer advances one node at a time, while the fast pointer advances two nodes at a time. By the time the fast pointer reaches the end, the slow pointer would have reached the splitting point (or near). Care must be taken to account those special cases. Below is a solution that works for all cases.

VN:F [1.9.22_1171]
Splitting Linked List, 3.6 out of 5 based on 5 ratings

### 9 responses to Splitting Linked List

1. seems like the line number 7 should move below 8.
7: slow = slow->next;
8: front_last_node = slow;
to keep the last node of the front.

VA:F [1.9.22_1171]
0
2. Why do you say this algorithm is better than scanning the lits twice? You're doing the same thing, only "concurrently" – I believe the runtime would be the same.

In fact, the "clever" algorithm will keep two memory blocks in cache, while the "naive" one will only keep one memory block in cache at the time, so it has a smaller "cache footprint".

VA:F [1.9.22_1171]
+1
• I agree. The improved version produces the same overhead. You still need to iterate through whole list with fast pointer and pass half of it with slow one.

VA:F [1.9.22_1171]
0
3. @1337c0d3r
I don’t think you need 3 pointers.You need them due to the structure of the

loop.
Using the following conditional form you need only 2 pointers, the slow and the fast and in the end of the loop the

is the start of the back list:
while(fast->next != NULL && fast->next->next!=NULL)

VA:F [1.9.22_1171]
0
4. I see that you need two extra pointers only (slaw , fast) to solve this problem, not three, just by checking for (fast.next != null).
this is my C# version using two extra pointers only:

void Split(Node head, ref Node first, ref Node last)
{
return; // Handle empty list

while (fast.next != null)
{
slow = slow.next;
fast = (fast.next != null) ? fast.next.next : null;
}
last = slow.next;
slow.next = null;
}

VN:F [1.9.22_1171]
0
• You don’t need to do it in this way. Because the number of elements is odd.

VN:F [1.9.22_1171]
0
• No, the number of elements not always be odd. The problem statement said: “If the number of elements is odd, the extra element should go in the front list. ” and this means it may be even. However, there are two problems in my code: 1)while (fast.next != null) should be while (fast != null). 2) after the loop last = slow.next; should be last = slow;

VN:F [1.9.22_1171]
0
5. VN:F [1.9.22_1171]
0