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; } |

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.

0ｎｏｐ

0can I start with fast advancing slow by one?i.e

*slow = head;

*fast = head-> next;

So only 2 pointers are used.

0verified my last post to be correct

0but more complicated than the above version so I prefer the above 3-pointer version

0Why 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".

+2I 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.

0@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)

+1I 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;

}

+1You don’t need to do it in this way. Because the number of elements is odd.

0No, 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;

0+1You do not need to handle one-node list before hand!!!!

0mine in java. hope it helps

0generic types is removed somehow..

0I need to do the same thing for school but I mus not creates new nodes. How can I do it????

Consider the SinglyLinkedList class partially given below. Instance variable head contains the address of the first node, and tail contains the address of the last node. Add to the SinglyLinkedList class a method Node void split() which will split the list into two sublists, one for the front half and one for the back half. If the number of elements is odd, the extra element has to go to the front list. For example splitting the list {2, 3, 5, 7, 11} should yield the two sublists {2, 3, 5} and {7, 11}. After the split the head” variable should contain the reference to the first node of the first list. Your method should return a reference to the first node of the second list. DO NOT create new nodes, just split the original list in two halves.

public class SinglyLinkedList

{

private class Node {

private Object data;

private Node next;

public Node ( ) {

data = null; next = null;

}

} // end of Node class

private Node head; // Reference to first node in the list

private Node tail; //Reference to the last node in the list

public SinglyLinkedList( ){

head = tail = null;

}

//other methods

} // end of SinglyLinkedList class

0Should that be List res = LinkedList() instead of List res = Arraylist()???

0Hey guys. I have this question for school. Please help me to do it!!!!

Consider the SinglyLinkedList class partially given below. Instance variable head contains the address of the first node, and tail contains the address of the last node. Add to the SinglyLinkedList class a method Node void split() which will split the list into two sublists, one for the front half and one for the back half. If the number of elements is odd, the extra element has to go to the front list. For example splitting the list {2, 3, 5, 7, 11} should yield the two sublists {2, 3, 5} and {7, 11}. After the split the

`head” variable should contain the reference to the first node of the first list. Your method should return a reference to the first node of the second list. DO NOT create new nodes, just split the original list in two halves.`

public class SinglyLinkedList

{

private class Node {

private Object data;

private Node next;

public Node ( ) {

data = null; next = null;

}

} // end of Node class

private Node head; // Reference to first node in the list

private Node tail; //Reference to the last node in the list

public SinglyLinkedList( ){

head = tail = null;

}

//other methods

} // end of SinglyLinkedList class

0In both op’s and the other’s posts, the input list (head) has been cut/changed. In this case, do we need a separated parameter for front (when the function returns, front === head) any way? I don’t see a declaration of the function, so I suggested use the following code.

0Thanks a lot Frank Wang……

0Hello guys.

I have this question for school. I have some problems to understand this algorithm.Can somebody help me with this. Thanks!!!

• Consider the following algorithm described in pseudo-code, which takes an array A of n positive integers as input and uses an initially-empty queue Q as an internal variable:

Let t 0

for i 0 to n – 1 do

if A[i] is an odd number then

Q.enqueue(A[i]).

else

while Q is not empty do

Let t t + Q:dequeue().

end while

end if

end for

while Q is not empty do

Let t t + Q:dequeue().

end while

Output t.

Please answer each of the following question concerning this algorithm:

(a) What is the output of this algorithm for the array A = {1, 9, 11, 14, 5, 3, 7, 13, 3, 12, 5}?

(b) Describe in one sentence what this algorithm computes.

(c) Characterize, using the big-Oh notation, the running time of the above algorithm in terms of n, the number of integers in A.

0Hello guys.

I have this question for school. I have some problems to understand this algorithm and the a,b,c questions below.Can somebody please help me with this???. Thanks!!!

• Consider the following algorithm described in pseudo-code, which takes an array A of n positive integers as input and uses an initially-empty queue Q as an internal variable:

Let t <- 0

for i <- 0 to n – 1 do

if A[i] is an odd number then

Q.enqueue(A[i]).

else

while Q is not empty do

Let t <- t + Q:dequeue().

end while

end if

end for

while Q is not empty do

Let t <- t + Q:dequeue().

end while

Output t.

Please answer each of the following question concerning this algorithm:

(a) What is the output of this algorithm for the array A = {1, 9, 11, 14, 5, 3, 7, 13, 3, 12, 5}?

(b) Describe in one sentence what this algorithm computes.

(c) Characterize, using the big-Oh notation, the running time of the above algorithm in terms of n, the number of integers in A.

0Yep the “smarter” solution is slower as it’s less cache-friendly.

0