java - Divide a linked list into half and return the second half

Question

This was a programming question that I did wrong.There was a partial code give as follows:

public class SingleLinkedList<E> {
   private Node<E> head;
   private int size = 0;

   private static class Node<E> {
     private E data;
     private Node<E> next;

     /** Creates a new node with a null next field
         @param dataItem  The data stored
     */
     private Node(E data) {
       data = dataItem;
       next = null;
     }

    /** Creates a new node that references another node
         @param dataItem  The data stored
         @param nodeRef  The node referenced by new node
     */
     private Node(E dataItem, Node<E> nodeRef) {
       data = dataItem;
       next = nodeRef;
     }
  }

}

My task was to create a method that divides the linked list in half leaving the first half of the elements in the original list and returning a new SingleLinkedList containing the second half of the list.If the number of elements is odd, then the extra element should go with the first half.I could not do it.Then my teacher gave answer like the following:

SingleLinkedList<E> newlist = new SingleLinkedList<E>();
 newlist.head =  temp.next; 
temp.next= null; 
return newlist

However, I'm not even getting the answer.I am a beginner.I would appreciate if someone can explain this problem.

Answer 1

The code which you have provided by your teacher is incomplete. Anyways I can give you two ways to find the pointer to second half:

1. If you want a pointer to refer second half in the same list.

   private static Node getSecondHalfInSameList(Node head) {
       Node fastRunner = head, slowRunner = head;
       while(fastRunner != null && fastRunner.next != null) {
           slowRunner = slowRunner.next;
           fastRunner = fastRunner.next.next;
       }
       return slowRunner;
   }
   

2. If you want to create a new list with all the nodes in the second half, then you can do the following.Here first we find the middle node then we will create a new list from second half by creating new node iterating from middle node to the end of the list.

   private static Node getSecondHalfByCreatingNewNodes(Node head) {
       Node mid = getMiddleNode(head);
       Node newHead = new Node(mid.data);
       mid = mid.next;
       Node tail = newHead, temp;
       while(mid != null) {
           temp = new Node(mid.data);
           tail.next = temp;
           tail = temp;
       }
       return newHead;
   }
   
   private static Node getMiddleNode(Node head) {
       Node fastRunner = head, slowRunner = head;
       while(fastRunner != null && fastRunner.next != null) {
           slowRunner = slowRunner.next;
           fastRunner = fastRunner.next.next;
       }
       return slowRunner;
   }