Amazon Interview Question
Software Engineer / DevelopersNo, I misunderstood the problem.
The simplest way that I can think of is,
1. count the number of elements in the list (n).
2. delete the (n - k + 1)th element of the list.
I assume it should be done in a single-pass
// assuming k is valid
ListNode* deleteKthNodeFromBack(ListNode* head, int k)
{
if (head == NULL) return head;
ListNode* fast (head), slow (head) slowPrev (NULL);
while (--k) fast = fast->next;
while (fast->next != NULL) {
slowPrev = slow;
slow = slow->next;
fast = fast->next;
}
if (slowPrev == NULL) head = slow->next;
else slowPrev->next = slow->next;
delete slow;
return head;
}
public static Elem head;
public static int DeleteKth(Elem elem,Elem prev,int k) {
int count = 0;
if (elem != null) {
count = DeleteKth(elem.sled,elem, k)+1;
if (count == k) {
if (prev == null) head = elem.sled;
else prev.sled = elem.sled;
}
}
return count;
}
// call with
DeleteKth(head, null, 2); where 2 is kth to be deleted
traverse the linked list and, when the kth element is found, fix the next-pointer of the previous and next element. of course you have to take care of the corner cases such as when there are less than k elements.
- Anonymous July 25, 2008