Microsoft Interview Question for Program Managers Interns


Country: India




Comment hidden because of low score. Click to expand.
4
of 6 vote

It would be a two step process.

1. In step 1, start two pointers, one moving ahead one node at a time and the other two nodes at a time. This lets us find out the middle and the last element.
2. In step 2, using 3-pointer mechanism that points to previous, current and next nodes, delete the given node. Handle the special case of adjusting the pointers if the deleted node is the middle node.(The middle and last-element pointers obtained in step 1 are used here) Otherwise fix, the pointers or previous, current and next nodes regularly along with fixing the pointer to the middle node from the last node.

- Murali Mohan August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 votes

I am sorry, but this will not work. How would your Step 1 find the middle and the last when there is a loop in the LL?
Even Step 2 is wrong. You don't really need to care if you are deleting a middle node or any other node. Yes, there will be special handling if the node to be deleted is the last node to restore the loop.

- sushant.singh1987 May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

SushantSingh1987 are you mad bro ? If u delete a node, then size of the linked list changes and so does the middle element in some cases. For example if there are 9 nodes and u delete any node, then size is 8, so middle element remains the same. But if there are 10 nodes and you delete 1, the the new middle is the previous node of the current middle. Hope you understand the point

- Rakesh Mondal October 03, 2014 | Flag
Comment hidden because of low score. Click to expand.
4
of 4 vote

**TO FIND THE LAST AND MIDDLE NODE**

1. use the fast and slow pointer to find a node in loop
2. count the number of nodes in the loop
3. if the count is k then ther are two possibilities
1. there are k+(k-1) nodes in sll
2. there are 2k nodes in sll
4. with this find the middle and last node of the sll
**DELETE THE GIVEN NODE**
now the delete the node, and point the last node to
1. if length of sll is odd, to the previous node
2. if even point to the next node

correct me, if i am wrong

- saran August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

: 4. with this find the middle and last node of the sll

how do you achieve this? how do you know which of the two possibilities from step 3 we have here?

- anon123 September 18, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

your answer works except for the logic to find the middle and last node.

- sushant.singh1987 May 14, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not sure we need this, Every time you delete the node, you are decrementing the count. So cant we just adjust the last node pointer to previous one.

2. if even point to the next node

- Vib December 31, 2014 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

u dont need to traverse twice..in the very first step, remove the node if you find it and rearrange it. u'll eventually end up pointing to the new last and middle.

- Anonymous August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

package oracle.prakash.investmentbank.test;

public class MicrosoftStack<T extends Comparable> {
public MicrosoftStack() {
super();
}

public MicrosoftStack(T data) {
this.setData(data);
}

private MicrosoftStack<T> next;
private MicrosoftStack<T> prev;
private int count;
private MicrosoftStack<T> mid;
private MicrosoftStack<T> head;
private MicrosoftStack<T> tail;
private T data;

public static void main(String[] args) {
MicrosoftStack<Integer> microsoftStack = new MicrosoftStack<Integer>();
int[] ints = { 20, 30, 40, 50, 60, 70, 80,90 };
for (int i : ints) {
microsoftStack.push(i);
}
microsoftStack.traverse();
System.out.println("---------------------------------------");
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead().getData());
System.out.println(microsoftStack.getTail().getData());
System.out.println(microsoftStack.getMid().getData());
System.out.println("---------------------------------------");
System.out.println(microsoftStack.pop());
System.out.println(microsoftStack.getHead());
System.out.println(microsoftStack.getTail());
System.out.println(microsoftStack.getMid());
}

public void push(T data) {
MicrosoftStack<T> item = new MicrosoftStack<T>(data);
this.setCount(this.getCount() + 1);
if (this.getHead() == null) {
this.setHead(item);
this.setMid(item);
this.setTail(item);

} else {
item.setNext(this.getHead());
this.getHead().setPrev(item);
this.setHead(item);
if (this.getCount() % 2 != 0) {
this.setMid(this.getMid().getPrev());
}
this.getTail().setNext(this.getMid());
}

}

public T pop() {
T data = null;
if (this.getHead() == null)
return null;
MicrosoftStack<T> head = this.getHead();
data = head.getData();
this.setCount(this.getCount() - 1);
this.setHead(head.getNext());
head.setNext(null);
if (this.getCount() % 2 != 0) {
this.setMid(this.getMid().getNext());

}

this.getTail().setNext(this.getMid());
if(this.getCount()==0) {
this.setHead(null);
this.setTail(null);
this.setMid(null);
}
return data;
}

public void traverse() {
MicrosoftStack<T> head = this.getHead();
while (head != null) {
System.out.println(head.getData());
head = head.getNext();
if (head.getData().equals(this.getTail().getData())) {
System.out.println(head.getData());
break;
}
}
}

public void setNext(MicrosoftStack<T> next) {
this.next = next;
}

public MicrosoftStack<T> getNext() {
return next;
}

public void setPrev(MicrosoftStack<T> prev) {
this.prev = prev;
}

public MicrosoftStack<T> getPrev() {
return prev;
}

public void setCount(int count) {
this.count = count;
}

public int getCount() {
return count;
}

public void setMid(MicrosoftStack<T> mid) {
this.mid = mid;
}

public MicrosoftStack<T> getMid() {
return mid;
}

public void setHead(MicrosoftStack<T> head) {
this.head = head;
}

public MicrosoftStack<T> getHead() {
return head;
}

public void setTail(MicrosoftStack<T> tail) {
this.tail = tail;
}

public MicrosoftStack<T> getTail() {
return tail;
}

public void setData(T data) {
this.data = data;
}

public T getData() {
return data;
}
}

- Prakash Barri August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi,
I need a clarification from Saran.
Are we given access to only the node we need to delete and nothing else. What I mean here is in a SLL it is possible to delete a node with just the information of the node to be deleted and nothing else such as head , tail etc. Is such info available here
Thanks

- Nomad August 06, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

We are provided with head and the value of the node to be deleted..(assume there is no duplicate elements)

- saran August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I can think of two things here:
1. we have to maintain the property that last node is pointing to middle node, so when any node is deleted, change the last node pointer to one node in backward direction.
2. Delete the node and reset the pointers, for this we need to traverse the linked list and keep two pointers prevNode and currentNode. Once we find the node to be deleted then delete that node and reset the pointers.

- OTR August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

find the middle element with slow and fast runner for a circularly linked list. find element that is before and after middle element. find lastElement by traversing until .next is the middle element for the second time. When deleting


if(even && element to be delete occurs before middle) {
middle = afterMiddle;
}
else if(odd && element to be delete occurs after middle) {
middle = beforeMiddle;
}

- Ronald August 07, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Last element will be anyway pointing to middle element so is finding middle node required? I think we should just find out where loop is starting, and that will be middle node. But looks like finding middle node is easier than finding loop.

- OTR August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

finding the middle element is exactly the start of the loop. the reason I say we should find the last element because you have to reset that pointer to the next "middle" element when you delete.

- Ronald August 07, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Let's split the question into two parts :

1. One is to delete any node in the linked list.
2. To make the last node of a linked list point to the middle element.

First delete the node in the linked list in O(n) time.
Next start from the head node using two pointers, slow and fast.
Slow moves one node at a time and fast moves two nodes at a time.
When fast reaches the end of the list, slow will be pointing to the middle element in the list. Make the last node point to slow and we're done.

- somesh August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

You need to consider that the list doesnt have any end.

- Raghav Grover August 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

but what if we are deleting the middle node or last node in the first step and also, it is not necessary that the second step's procedure returns the middle node

- Prav August 11, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

First find the middle node in the list
Make count no of elements on left and right of middle node (Node_left, Node_right)
(Node_left, Node_right) could be equal or Node_left = Node_right-1
Now when delete the random node in the list check if it is right or left of the middle node,
and change this count
on the basis of this count you have to then move middle right or left
if(Node_left < Node_right-1 )
move right
else if(Node_right <Node_left)
move left

- moron August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think here we can use 3 pointers
mid, mid_prev, mid_next move these pointers accordingly to get mid.

- PB August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can take it with the cases:

Step 1: Try to find out the middle node and also the number of the nodes in the linked list whether they are even or odd.

How to: Start from Head (using fast and the slow pointers).
if fast -> next == slow (Then the number of nodes would be odd).
else if (fast->next->next == slow) then the number of nodes would be even.
Now after this iteration we would be able to get the pointer to the middle element and also to the last element in the linked list.

Step 2: Remove the node:

How To: Go to the desired node.
if the number of nodes are odd then after removal of the desired node the number of nodes would be even so the location of the middle element wont change.

In case there are odd nodes currently then the new middle node would be the node previous to the current middle node.

Note: Some special cases have to be taken care of.
1. If the desired node itself is the middle element.
2. If the desired node is the last element in the linked list.

- Anonymous August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

ListNode* delete(ListNode* head, int key)
{
         if (head == NULL) return head;
         ListNode* slow = head, fast = head->next, slowPrev = NULL;
         while (fast->next != slow)
         {
              slow = slow->next;
              fast = fast->next;
              if (fast->next != slow ) fast = fast->next;
         }
          fast->next = NULL // change the last to new middle and now try to delete the element. 

         ListNode* h = head, prev = NULL; 
         while (h != NULL ) {
                     if (h->val = key) { 
                              if (h == new_middle) {
                                      if (prev == NULL) { head = h->next; }
                                      else { prev->next = h->next; last->next = h->next; }
                                      break;     
                              }
                             if (h == last) {
                                         prev->next = new_middle;
                                         delete h;
                             }
                             else { prev->next = h->next; delete h; break; } 
                              
                     }
                     else if (h == last) break; 
                     else  { h = h->next; } 
         }
         return head; 
}

- Anonymous August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we do it this way :--
(I m assuming that we know the number of nodes in the list. If not we can find it easily using cycle finding algo in the list.)
1. Simply delete the required node first as in SLL.
2. Now we know how many nodes remain in the list. Based on this restore the last node pointer which is pointing to the middle node.

- Anonymous August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can we do it this way :--
(I m assuming that we know the number of nodes in the list. If not we can find it easily using cycle finding algo in the list.)
1. Simply delete the required node first as in SLL.
2. Now we know how many nodes remain in the list. Based on this restore the last node pointer which is pointing to the middle node.

- gg August 11, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The crux of this problem is how u traverse backward in single link list .

- yash August 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The crux of this problem is how u traverse backward in single link list

- yash August 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

i think thr will be several cases (after finding mid,end)
1 if node to be deleted is head : see if its mid
2.if node to be deleted is end : change end ptr
3.if node to be deleted is mid : see if odd length(mid will change to prev to mid) and if even length(mid will change to next to mid)
4.if node to be deleted is other : see if b4 mid(see if odd length then mid will change) else if after mid (see if even length then mid will not change)

tell if wrong line of thinking!

- mg August 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

last line typo.it is : .if node to be deleted is other : see if b4 mid(see if even length then mid will change) else if after mid (see if odd length then mid will change)

- mg August 20, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Can be done as following:

1. use two pointers with x and 2x speed to find the mid node and whether the length of array is even or odd.
2. traverse the list for second time to find the node to delete, while tracking if it comes before mid or not.
3. if length is odd and element to delete is mid or before mid, set newMid to next of mid. If length is even and deleted element is mid or after mid set newMid to prev of mid.
4. delete the node. if newMid is not NULL, set the end of modified list to newMid.

#include<stdlib.h>

typedef struct list_s {
    int val;
    struct list_s *next;
} list;

list *delete(list *head, int val)
{
	if(head == NULL)
		return head;
	list *t1, *t2, *prev, *mid, *newMid = NULL;
	enum {even, odd} length;

	/*find the mid and length(odd/even) using two runners*/
	t1 = head;
	t2 = t1->next;
	while(t1 != t2 && t1 != t2->next){
		t1 = t1->next;
		t2 = t2->next->next;
	}
	if(t1 == t2)
		length = odd;
	else
		length =even;
	mid = t1;

	/*search for node to delete and track if node is previous to the mid*/
	enum {false, true} isPrevToMid = true;
	t1 = head;
	prev = NULL;
	while(t1->next != mid  || isPrevToMid = true){
		if(t1 == mid){
			isPrevToMid = false;
			/*if length is odd, newMid is prev element to mid*/
			if(length == odd)
				newMid = prev;
		}
		if(t1->val == val)
			break;
		prev = t1;
		t1 = t1->next;
	}

	/*if node not found, return the same list*/
	if(t1->val != val)
		return head;

	/*set newMid to next of mid if length is even and node to be deleted is prevToMid*/
	if((isPrevToMid == true || t1 == mid) && length == even)
		newMid = mid->next;

	if(prev == NULL){ 	/*if the node is head, modify the head*/
		if(head->next == head)
			head = NULL;
		else
			head = head->next;
	}
	else                /*else remove node from the list*/
		prev->next = t1->next;
	
	/* if newMid is not NULL, find the end node in the modified list and set it to newMid,*/
	if(newMid != NULL){
		t2 = t1;
		while(t2->next != mid || isPrevToMid == true){
			if(t2 == mid)
				isPrevToMid = false;
			t2 = t2->next;
		}
		t2->next = newMid;
	}

	free(t1);
	return head;
}

- karaamaati August 20, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Why make it complicated; when most (if not all) of the solutions require you to scan the list twice why not just follow the normal LL deletion logic.
1) scan the list and delete target node
2) scan the list and make last node point to the middle node (can achieve this by using slow and fast pointers)

- IntwPrep.MS December 17, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We will need two pointers 'fast' and 'slow' to iterate the list.
fast=fast->next->next;
slow=slow->next;
conditions to check
1. if (fast->next==slow) //the list has odd number of nodes.
2. if (fast->next->next==slow) //the list has even number of nodes.
Now we have pointer to middle node and a pointer to last node.
check if the node to be deleted is before or after the middle node or its middle node or last node.Proceed with deletion and update the list accordingly ( even and odd criteria as stated in problem)

- Harry June 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

It is the same as an deletion in an ordinary linked list.

- kevseb1993 July 20, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Logic is as follows:
Break the logic into two functions :
deleteNode(Node head, int k) and updateTailNext(Node head)

a) deleteNode(Node head, int k)
1. if(given value == head.data) ;
then update the head pointer, Linked List size --; return head;
2. else ,
create slow and fast pointer, fast pointer is one step ahead of slow pointer.
increment fast pointer until fast.data == given or fast ==null;
Linked List size --; return head;


b)updateTailNext(Node head)
(Note: index is 0 based)

if(size%2 == 0){
newMiddle = this.getNodeAtIndex((size -2)/2);
}else {
newMiddle = this.getNodeAtIndex((size)/2);
}

public class DeleteNodeTailMiddle extends LinkedList {

	public Node deleteNode(Node head, int k){
		int size = this.getSize();
		Node slow = head;
		Node fast =head;
		
		if(head.data == k){
			head = head.next;
			size --;
			this.setHead(head);
			this.setSize(size);
			return head;
		}
	
		while(fast != null && fast.data != k){
			slow =fast;
			fast = fast.next;
		}
		
		slow.next = fast.next;
		fast = null;
		size --;
		this.setSize(size);
	
		return head;
			
}
	
	public Node updateTailNext(Node head){
		int size = this.getSize();
			
		Node Tail =this.getNodeAtIndex(size-1);
		
		Node newMiddle ;
		
		if(size%2 == 0){
			newMiddle = this.getNodeAtIndex((size -2)/2);
		}else {
			newMiddle = this.getNodeAtIndex((size)/2);
		}
		
		System.out.println("newMiddle is   :" + newMiddle.data +"\n");
		Tail.next = newMiddle;
		
		return head;
	}
	
	
	public static void main(String[] args){
		
		DeleteNodeTailMiddle l = new DeleteNodeTailMiddle();
		 l.add(0,10);
		   l.add(1,12);
		   l.add(2,2);
		   l.add(3,3);
		   l.add(4, 45);
		   
		      
		   
		   System.out.println("After adding elements \n");
		   l.display();
		   
//Set the loop/ set the last node's next to the middle node in given input
		    Node head = l.getHead();
		    Node head2 = l.updateTailNext(head);

//delete the Node with value k = 45
		     int k = 45;
		   Node head3 = l.deleteNode(head2, k);
		   Node head4 = l.updateTailNext(head3);
		    	   
	}
}



public class LinkedList {
private Node head;
private int size;
 
 public LinkedList(){
	 head =null;
 }

public void add(int index, int value){
		if(index ==0){
			Node tmp = new Node(value);
			tmp.next = head;
			head= tmp;
			size ++;
		}else{
			Node current = goTo(index-1);
			Node newNode = new Node(value);
			newNode.next = current.next;
			current.next =newNode;
			size ++;
		}
	}

public Node getNodeAtIndex(int x){
	Node node = this.getHead();
	int size= getSize();
	if(x>size){
		return null;
	}
	  for (int i =0;i<size;i++){
		if(i== x){ break;}
		node = node.next;
	}
	  return node;
}

public void setSize(int size){
	this.size = size;
}

public void setHead(Node h){
	head = h;
}

}

- pnd1901 October 19, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

void printList(){
lNode curr = head;
lNode mid = head;
lNode prev = null;
int count = 0;
while(curr!=null){
System.out.println(curr.value + " ");
if(curr.next==null){
curr.next = mid;
}
if(count%2==0){
prev = curr;
curr=curr.next;
}
else{
prev=curr;
curr=curr.next;
mid = mid.next;
}
count++;

}

You can do normal delete function and when accessing the list, call this function.

- Ab August 08, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

Please read the question. It is given that the circular linked list's last node points to middle node,you can't traverse till curr!=NULL,you'll end up in indefinite loop :)

- Avenger August 08, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

**TO FIND THE LAST AND MIDDLE NODE**

1. use the fast and slow pointer to find a node in loop
2. count the number of nodes in the loop
3. if the count is k then ther are two possibilities
1. there are k+(k-1) nodes in sll
2. there are 2k nodes in sll
4. with this find the middle and last node of the sll
**DELETE THE GIVEN NODE**
now the delete the node, and point the last node to
1. if length of sll is odd, to the previous node
2. if even point to the next node

comment if anything wrong.

- saran August 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Not exactly.
The steps should be as follows:
1. use a fast and a slow pointer to find the middle node and the last node and the node before the middle node, and also count the number of nodes in the list.
2. from the head, find the node containing the target value, and its previous node.
3. adjust the next pointer of the last node.
4. delete the target node.

public class LinkedListNode
{
	public LinkedListNode next=null;
	public int val=Integer.MIN_VALUE;
	
	public LinkedListNode(int v)
	{
		this(v, null);
	}
	public LinkedListNode(int v, LinkedListNode node)
	{
		val=v;
		next=node;
	}
	public String toString()
	{
		return String.format("[LinkedListNode: val=%d]", val);
	}
	public String toStringAll()
	{
		return String.format("[LinkedListNode: val=%d, next=%s]", val, (next!=null) ? next.toStringAll() : null);
	}
}
public class ID24819662
{
	public LinkedListNode delete(LinkedListNode head, int target)
	{
		if (head==null)
			return null;
		else if (head.next==head)
		{// only one node
			if (head.val==target)
				return null;
			else
				return head;
		}
		else if (head.next.next==head)
		{// two nodes
			LinkedListNode node=head;
			while (node.val!=target)
			{
				node=node.next;
				if (node==head)// no target node
					return head;
			}
			if (node==head)
			{
				LinkedListNode newHead=head.next;
				newHead.next=newHead;
				return newHead;
			}
			else
			{
				head.next=head;
				return head;
			}
		}
		// 1. use a fast and a slow pointer to find the middle node 
		// and the last node and the node before the middle node,
		// and also count the number of nodes in the list.
		LinkedListNode beforeMiddle=null;
		LinkedListNode middle=null;
		LinkedListNode last=null;
		LinkedListNode slow=head;
		LinkedListNode fast=head;
		int countNodes=1;
		while (true)
		{
			beforeMiddle=slow;
			slow=slow.next;
			fast=fast.next.next;
			countNodes += 2;
			if (fast.next==slow)
			{// odd number of nodes
				middle=slow;
				last=fast;
				break;
			}
			else if (fast.next.next==slow)
			{// even number of nodes
				countNodes++;
				middle=slow;
				last=fast.next;
				break;
			}
		}
		// 2. from the head, find the node containing the target value, and its previous node.
		LinkedListNode previous=null;
		LinkedListNode node=head;
		boolean passedMiddle=false;
		while (true)
		{
			if (node==middle)
				passedMiddle=true;
			if (node.val==target)
				break;
			previous=node;
			node=node.next;
			if (passedMiddle && node==middle)// no such node found
				return head;
		}
		LinkedListNode newHead=(node==head) ? head.next : head;
		// 3. adjust the next pointer of the last node
		if (!passedMiddle)
		{
			if ((countNodes&1)==0)// even number of nodes
				last.next=middle.next;
			// if odd number of nodes, do nothing
		}
		else if (node==middle)
		{
			if ((countNodes & 1) == 1)// odd number of nodes
				last.next = beforeMiddle;
			else
				last.next=middle.next;
		}
		else if (passedMiddle)
		{
			if ((countNodes&1)==1)// odd number of nodes
				last.next=beforeMiddle;
			// if even number of nodes, do nothing
		}
		// 4. delete the node
		if (previous!=null)
			previous.next=node.next;
		return newHead;
	}
	
	public static void main(String[] args)
	{
		LinkedListNode head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		
		System.out.println(head.toString());
		ID24819662 wpd=new ID24819662();
		wpd.delete(head, 4);
		
		head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		wpd.delete(head, 10);
		
		head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		wpd.delete(head, 2);
		
		head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		wpd.delete(head, 0);
		
		head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		wpd.delete(head, 1);
		
		head=new LinkedListNode(0, 
				new LinkedListNode(1, 
				new LinkedListNode(2, 
				new LinkedListNode(3,
				new LinkedListNode(4,
				new LinkedListNode(5))))));
		head.next.next.next.next.next.next=head.next.next;
		wpd.delete(head, 5);
	}
}

- wangpidong October 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
-2
of 2 vote

So isn't there a much simpler solution than looping through the list? I believe so.

First let's utilize a list.size() function to return the size of the list. That will help us find even/odd.

Now when a node is deleted from anywhere in the list, we find the middle element via:

if(list.size() %2 == 0)
mid = list.size()/2
else
mid = ciel(list.size()/2)

Note that the ciel function rounds up to the next largest int. You could also allow it to divice, truncate the remainder, then simply add 1.

Either way, we now know our middle location based on the size of the list after deletion. Now simply iterate through your list to that element (mid) and set the end node mid-pointer to that.

If our list has a built in pointer to the end, this becomes very easy as we do not need to loop through to find the end. We do have to design for the edge case that occurs when we delete the end node though.

- masterjaso August 08, 2013 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More