Alcatel Lucent Interview Question
Software Engineer / DevelopersCountry: India
Interview Type: In-Person
@Test
public void deleteNthNodeFromEnd() {
LinkList lis = populateLinkList();
int n = 3;
Node pointer1 = lis.getHead();
Node pointer2 = lis.getHead();
Node pointer3 = lis.getHead();
int i = 1;
while(pointer1.getNext()!=null) {
if(i<n){
pointer1 = pointer1.getNext();
++i;
} else {
pointer1 = pointer1.getNext();
pointer3 = pointer2;
pointer2 = pointer2.getNext();
}
}
pointer3.setNext(pointer2.getNext());
lis.printList();
}
public class Node {
Node next;
Object data;
public Node(Object dataValue) {
next = null;
data = dataValue;
}
public Node(Object dataValue, Node nextValue) {
next = nextValue;
data = dataValue;
}
public Object getData() {
return data;
}
public void setData(Object dataValue) {
data = dataValue;
}
public Node getNext() {
return next;
}
public void setNext(Node nextValue) {
next = nextValue;
}
}
public class LinkList {
private Node head;
public LinkList() {
head = null;
}
public Node getHead() {
return head;
}
public void setHead(Node head) {
this.head = head;
}
public void insert(Object dataValue) {
if(head==null) {
head = new Node(dataValue);
} else {
Node newNode = new Node(dataValue,head);
head = newNode;
}
}
public boolean isEmpty(){
return head == null;
}
public void printList() {
Node currentLink = head;
System.out.print("List: ");
while(currentLink != null) {
System.out.println(currentLink.data.toString());
currentLink = currentLink.getNext();
}
System.out.println("");
}
public void delete(){
head = head.getNext();
}
}
here is an optimum way to delete the Kth node from last..
public void deleteK(int k){
Link<Integer> current = head;
Link<Integer> previous = head;
for(int i=0;i<k;i++){
current = current.next;
if(current == null)
return;
}
while(current.next != null){
previous = previous.next;
current = current.next;
}
previous.next = previous.next.next;
}
Please do let me know in case of any improvement..
You can always count the number of nodes first then have another pass for removing. A more efficient way is to start with two pointers n nodes apart. when the second pointer reaches the end, return the node pointed to by the first pointer
- Anonymous May 18, 2014