Splitting 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.

VN:F [1.9.22_1171]
Rating: 3.9/5 (15 votes cast)
Splitting Linked List, 3.9 out of 5 based on 15 ratings

23 thoughts on “Splitting Linked List

  1. Anonymous

    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. ripper234

    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]
    +2
    1. Anatoliy

      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. reader

    @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]
    +1
  4. Mahmoud Wahdan

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

    VN:F [1.9.22_1171]
    +1
      1. Mahmoud Wahdan

        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. Brady Fang

    VN:F [1.9.22_1171]
    +1
  6. Ralph

    mine in java. hope it helps

    VN:F [1.9.22_1171]
    0
    1. Nataly

      I 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

      VA:F [1.9.22_1171]
      0
  7. Nataly

    Hey 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

    VA:F [1.9.22_1171]
    0
  8. Frank Wang

    In 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.

    VN:F [1.9.22_1171]
    0
  9. Nataly

    Hello 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.

    VA:F [1.9.22_1171]
    0
  10. Nataly

    Hello 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.

    VA:F [1.9.22_1171]
    0

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use the <code> tag to embed your code.

*