Given the head of a singly linked list and an integer k, split the linked list into k consecutive linked list parts. The length of each part should be as equal as possible: no two parts should have a size differing by more than one. This may lead to some parts being null. The parts should be in the order of occurrence in the input list, and parts occurring earlier should always have a size greater than or equal to parts occurring later. Return an array of the k parts. Example 1: Example 2: Constraints: For C++ and Python Solution Click HereProgram Code
Java
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 newlistHowever, I'm not even getting the answer.I am a beginner.I would appreciate if someone can explain this problem.
I have been asked to design a method splitMid that can be added to the LinkedList<E> class.
This method should have the following header:
public void splitMid(LinkedList<E> sublist)
and should split the given list into two sub-lists of (almost) equal sizes. Suppose myList points to the with elements 34,65,27,89 and 12. The statement myList.splitMid(sublist); should split myList into two sublists: myList --> 34,65 and 27
sublist --> 89,12
----------------------------------------------------------------------------------------
I have made the foolwing assumptions: 1)The head of a linkedlist always points to the first node. 2)Create a new head pointer for the second linkedlist.
3)Traverse through the linkedlist and find where you want to split the list and assign the pointer to that node variable midPoint and set the next pointer of previous node to null.
I have aome problems to complete this task. Any suggestions and guidelines would be appreciated.
Here is my code:
class SplitLinkedList:
import java.util.LinkedList; public class SplitLinkedList<E> { public void splitMid(LinkedList<E> sublist) { Node midPoint = nodeBefore.next; // get the midpoint LinkedList n = new LinkedList(); n.head = midPoint; // head pointer for the second linked list for(int i = 0; i < n.size(); ++i) { } } }class TestSplitLinkedList:
import java.util.LinkedList; public class TestSplitLinkedList<E> { public void main(String args[]) { LinkedList<Integer> myList = new LinkedList<Integer>(); SplitLinkedList sublist = new SplitLindedList(); myList.addLast(34); myList.addLast(65); myList.addLast(27); myList.addLast(89); myList.addLast(12); myList.splitMid(sublist); } }java
Recommended Answers
I have some problems to complete this task.
Please post your questions and problems.
Hi Norm. My main problem is how I can split the LinkedList. I thought using the % operator could you tell me your opiinion.
In addition I am receiving the followng errors:
For:
SplitLinkedList sublist = new SplitLindedList(); Multiple markers at this line - SplitLindedList cannot be resolved to a type - SplitLinkedList is a raw type. References to generic type SplitLinkedList<E> should be parameterizedFor:
myList.splitMid(sublist); The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>For:
Node midPoint = nodeBefore.next; Multiple markers at this line - nodeBefore cannot be resolved to a variable - Node cannot be resolved to a typeFor:
n.head = midPoint; head cannot be resolved or is not a field
Can you post the errors as they are printed by the compiler? Your edited postings do not show the full text of the error message.
Exception in thread "main" java.lang.Error: Unresolved compilation problems: SplitLindedList cannot be resolved to a type The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer> at TestSplitLinkedList.main(TestSplitLinkedList.java:10)
Where is the class: SplitLindedList defined?
Norm I meant SplitLinkedList so this is ok now. The next error is:
Exception in thread "main" java.lang.Error: Unresolved compilation problem: The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer> at TestSplitLinkedList.main(TestSplitLinkedList.java:19)
The method splitMid(SplitLinkedList) is undefined for the type LinkedList<Integer>
What don't you understand about that message?
Where is that method defined in the LinkedList class?
Hi Norm I have changed quite a lot my code the last 2 days and I came up with the following code:
UnorderedLinkedList class:
import java.util.LinkedList.*; import java.util.*; public class UnorderedLinkedList<E extends Comparable<? super E>> extends LinkedList<E> { public void splitMid(LinkedListClass<E> sublist) { LinkedListNode<E> current; LinkedListNode<E> mid; int i; if (first == null) { sublist.first = null; sublist.last = null; sublist.count = 0; } else if (first.link == null) { sublist.first = null; sublist.last = null; sublist.count = 0; } else { mid = first; current = first.link; i = 1; if (current != null) current = current.link; while (current != null) { mid = mid.link; current = current.link; i++; if (current != null) current = current.link; } sublist.first = mid.link; sublist.last = last; last = mid; last.link = null; sublist.count = count - i; count = i; } } }class TestSplitLinkedList:
public class TestSplitLinkedList{ public static void main(String[] args) { UnorderedLinkedList<Integer> myList = new UnorderedLinkedList<Integer>(); UnorderedLinkedList<Integer> sublist = new UnorderedLinkedList<Integer>(); myList.addLast(34); myList.addLast(65); myList.addLast(27); myList.addLast(89); myList.addLast(12); myList.splitMid(sublist); //myList.splitMid(sublist); } }I am receiving the following error:
Exception in thread "main" java.lang.Error: Unresolved compilation problem: The method splitMid(LinkedListClass<Integer>) from the type UnorderedLinkedList<Integer> refers to the missing type LinkedListClass at TestSplitLinkedList.main(TestSplitLinkedList.java:22)
Can you compile the program and get an error message from the compiler?
Your IDE's message is confusing.
Where is LinkedListClass defined?
I am using the inbuild LinkedList class Norm.
Shall I create my own linkedlist class?
public void splitMid(UnorderedLinkedList<E> sublist)
I have change the parameter of the method my errors now are:
Exception in thread "main" java.lang.Error: Unresolved compilation problems: LinkedListNode cannot be resolved to a type LinkedListNode cannot be resolved to a type first cannot be resolved to a variable first cannot be resolved or is not a field last cannot be resolved or is not a field count cannot be resolved or is not a field first cannot be resolved to a variable first cannot be resolved or is not a field last cannot be resolved or is not a field count cannot be resolved or is not a field first cannot be resolved to a variable first cannot be resolved to a variable first cannot be resolved or is not a field last cannot be resolved or is not a field last cannot be resolved to a variable last cannot be resolved to a variable last cannot be resolved to a variable count cannot be resolved or is not a field count cannot be resolved to a variable count cannot be resolved to a variable at UnorderedLinkedList.splitMid(UnorderedLinkedList.java:11) at TestSplitLinkedList.main(TestSplitLinkedList.java:22)
Where are all the variables/symbols in that list defined? You must define EVERY variable and class that you use in your program.
Otherwise the compiler will give you error messages.
Can you use the javac program to compile your program? Your IDE does not print out good error messages.
Hi Norm i hava design an implementation of a SinglyLinkedList and a splitMid method
public class SinglyLinkedList<T> { private class Node<T> { private T data; private Node<T> next; public Node(T data,Node<T> next) { this.data = data; this.next = next; } public T getData() { return data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } } private Node<T> head;//head of the linked list private Node<T> last; private int size; private int count; public SinglyLinkedList() { head = null; last = null; size = 0; count = 0; } public String toString() { String str = "["; Node<T> curr; for (curr=head;curr!=null;curr = curr.getNext()) { str = str + curr.getData(); if (curr.getNext()!=null) str = str + " "; } str = str + "]"; return str; } public void addFirst(T data) { Node<T> newnode = new Node<T>(data,head); head = newnode; size++; count++; } public void removeFirst() { Node<T> current = head; head = head.getNext(); //move head to the next element current.setNext(null); } public void addLast(T data) { Node<T> current; if (head==null) { addFirst(data); return; } current = head; while (current.getNext()!=null) current = current.getNext(); Node<T> newnode = new Node<T>(data,null); newnode = last; current.setNext(newnode); size++; count++; } public void add(int index,T data) { int i; if (index>size) return; if (head==null) { addFirst(data); return; } //step 1 Node<T> current; current = head; for (i=0;i<index-1;i++) { current = current.getNext(); } //current now refers to object immediately before new node //step 2 Node<T> newnode = new Node<T>(data,current.getNext()); //step 3 current.setNext(newnode); size++; count++; } public void remove(int index) { if ((index<0) || (index>=size)) return; Node<T> current,previous; current = head; previous = null; for (int i=0;i<index;i++) { previous = current; current = current.getNext(); } if (index!=0) previous.setNext(current.getNext()); else { head = head.getNext(); } size--; } public void splitMid(SinglyLinkedList<T> sublist) { Node<T> current; Node<T> mid; int i; if (head == null) { sublist.head = null; sublist.last = null; sublist.count = 0; } else if (head.getNext() == null) { sublist.head = null; sublist.last = null; sublist.count = 0; } else { mid = head; current = head; i = 1; if (current != null) current = current.getNext(); while (current != null) { mid = mid.getNext(); current = current.getNext(); i++; if (current != null) current = current.getNext(); } sublist.head = mid.getNext(); sublist.last = last; last = mid; last = null; sublist.count = count - i; count = i; } } public static void main(String[] args) { SinglyLinkedList<Integer> myList = new SinglyLinkedList<Integer>(); SinglyLinkedList<Integer> sublist = new SinglyLinkedList<Integer>(); myList.addLast(34); myList.addLast(65); myList.addLast(27); myList.addLast(89); myList.addLast(12); System.out.println( myList); // ListIterator<Integer> it = myList.listIterator(); // while(it.hasNext()) // { // System.out.println(it.next()); // } myList.splitMid(SinglyLinkedList<T> sublist); } }I am receiving the following error for this line:
myList.splitMid(SinglyLinkedList<T> sublist); Cannot find symbol - variable SinglyLinkedList
Look at what that statement is doing? Is it defining a method
or is it calling a method?
What is the correct syntax for what it is doing?
Norm thank you for your help and I hope that you had nice christmas. Here is my code and it works as I expexted.
SinglyLinkedList<T> class:
public class SinglyLinkedList<T> { private class Node<T> { private T data; private Node<T> next; public Node(T data,Node<T> next) { this.data = data; this.next = next; } public T getData() { return data; } public Node<T> getNext() { return next; } public void setNext(Node<T> next) { this.next = next; } } private Node<T> head;//head of the linked list private Node<T> last; private int size; private int count; public SinglyLinkedList() { head = null; last = null; size = 0; count = 0; } public String toString() { String str = "["; Node<T> curr; for (curr=head;curr!=null;curr = curr.getNext()) { str = str + curr.getData(); if (curr.getNext()!=null) str = str + " "; } str = str + "]"; return str; } public void addFirst(T data) { Node<T> newnode = new Node<T>(data,head); head = newnode; size++; count++; } public void removeFirst() { Node<T> current = head; head = head.getNext(); //move head to the next element current.setNext(null); count--; } public void addLast(T data) { Node<T> current; if (head==null) { addFirst(data); return; } current = head; while (current.getNext()!=null) current = current.getNext(); Node<T> newnode = new Node<T>(data,null); current.setNext(newnode); size++; count++; } public void add(int index,T data) { int i; if (index>size) return; if (head==null) { addFirst(data); return; } //step 1 Node<T> current; current = head; for (i=0;i<index-1;i++) { current = current.getNext(); } //current now refers to object immediately before new node //step 2 Node<T> newnode = new Node<T>(data,current.getNext()); //step 3 current.setNext(newnode); size++; count++; } public void remove(int index) { if ((index<0) || (index>=size)) return; Node<T> current,previous; current = head; previous = null; for (int i=0;i<index;i++) { previous = current; current = current.getNext(); } if (index!=0) previous.setNext(current.getNext()); else { head = head.getNext(); } size--; count--; } public void splitMid(SinglyLinkedList<T> sublist) { Node<T> current; Node<T> mid; int i; if (head == null) { sublist.head = null; sublist.last = null; sublist.count = 0; } else if (head.next == null) { sublist.head = null; sublist.last = null; sublist.count = 0; } else { mid = head; current = head.next; i = 1; if (current != null) current = current.next; while (current != null) { mid = mid.next; current = current.next; i++; if (current != null) current = current.next; } sublist.head = mid.next; sublist.last = last; last = mid; last.next = null; sublist.count = count - i; count = i; } } public static void main(String[] args) { SinglyLinkedList<Integer> myList = new SinglyLinkedList<Integer>(); SinglyLinkedList<Integer> sublist = new SinglyLinkedList<Integer>(); myList.addLast(34); myList.addLast(65); myList.addLast(27); myList.addLast(89); myList.addLast(12); System.out.println("My original myList: " + myList); myList.splitMid(sublist); System.out.println("myList after calling splitMid: " + myList); System.out.println("sublist is: " + sublist); } }Output:
My original myList: [34 65 27 89 12] myList after calling splitMid: [34 65 27] sublist is: [89 12]