In the class LinkedList below, implement the method LinkedList partition(E elem)
ID: 3918863 • Letter: I
Question
In the class LinkedList below, implement the method LinkedList partition(E elem). This instance method partitions this list in two parts. This intance retains all the leftmost elements of this list up to and including the first occurrence of elem. The rest of the elements are returned as a new list. If elem is not found in the list, then this list remains intact and the returned list is empty. For instance, let xs designate a list containing the values 1, 2, 3, 4, 3, 5, 6. After the call ys = xs.partition(3), the list designated by xs contains the elements 1, 2, 3, whereas ys now designates a list containing the elments 4, 3, 5, 6. The method must be implemented following the technique presented in class for implementing recursive methods inside the class, i.e. where a recursive method is made of a public part and a private recursive part, which we called the helper method. The public method initiates the first call to the recursive method.
Explanation / Answer
// assuming Node is like below: class Node { int data; Node next; } // partition method is in linkedlist class below class LinkedList { // assuming class has some pointer for head Node head; // main partition method Node partition(int value) { return partition(value, head); } // helper method for making the partition private Node partition(int value, Node start) { // if(start == null) { return start; } // if data on start node is what we want, // break the list.. if(start.data == value) { return start.next; } else { return partition(value, start.next); } } }