Wednesday 13 August 2014

Delete the Middle Element from a Linked List and second problem Divide the List around a given value.

class Node{
private int data;
private Node next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
}

public class LL {
private Node head;private int length;
public static void main(String[] args) {
LL l1 = new LL();
l1.add(12);l1.add(20);l1.add(6);l1.add(12);l1.add(20);l1.add(6);
l1.printList();System.out.println();
Node md = l1.head;
for(int i=0;i<l1.length/2-1;i++){md=md.getNext();}
l1.deleteMiddle(md);System.out.println();
l1.printList();
l1.divideListAround(13);System.out.println();
l1.printList();

}


private Node createNode(int data){
Node newNode = new Node();newNode.setData(data);newNode.setNext(null);return newNode;
}


private void add(int data){ 
length++;
Node nn = createNode(data);
if(this.head==null){ this.head=nn; }
else
{
Node temp = this.head;
while(temp.getNext()!=null)temp=temp.getNext();
temp.setNext(nn);
}
}


private void printList(){
   Node head = this.head;
   while(head!=null){System.out.print(head.getData()+"->");head=head.getNext();}
}

// We assume that reference to the node is given:O(1) time to do that.
private void deleteMiddle(Node mid){
length--;
mid.setData(mid.getNext().getData());
mid.setNext(mid.getNext().getNext());
}


private void divideListAround(int val){
LL left = new LL();
LL right = new LL();
Node h = head;
while(h!=null){
if(h.getData()<val)
left.add(h.getData());
else
right.add(h.getData());
h=h.getNext();
}
//Merge the lists
Node headLeft = left.head;
while(headLeft.getNext()!=null)
{
headLeft=headLeft.getNext();
}
headLeft.setNext(right.head);
this.head=left.head;
}

}

No comments:

Post a Comment