Splitting Linked List
September 11, 2010 in linked list
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void FrontBackSplit(Node *head, Node **front, Node **back) { if (!head) return; // Handle empty list Node *front_last_node; Node *slow = head; Node *fast = head; while (fast) { front_last_node = slow; slow = slow->next; fast = (fast->next) ? fast->next->next : NULL; } front_last_node->next = NULL; // ends the front sublist *front = head; *back = slow; } |
Anonymous said on January 12, 2011
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.
ripper234 said on February 15, 2011
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".
Anatoliy said on August 16, 2011
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.
reader said on March 11, 2012
@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)
Mahmoud Wahdan said on December 7, 2012
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)
{
if (head == null)
return; // Handle empty list
Node slow = head;
Node fast = head;
while (fast.next != null)
{
slow = slow.next;
fast = (fast.next != null) ? fast.next.next : null;
}
last = slow.next;
slow.next = null;
first = head;
}
wintersliu said on May 12, 2013
You don’t need to do it in this way. Because the number of elements is odd.