Amazon Interview Question
Country: United States
Important thing to note: This question demands for reversing a linked list, followed by the return of the _tail_ element (unlike usual reversal, which requires the return of the head).
Please ignore any comments/code using the "this" operator. That is something I need for this function to work with my class.
Edge case left as exercise: The original input list, is of length less than k. I'd recommend adding a small while loop in the beginning of the above function that counts till (currHead.getNext() == null || elemCount >= k)
void reverse_every_k(Node*& head, int k)
{
Node *prev, *cur, *tmp, *new_head;
prev = NULL; cur = head;
while( cur ) {
*tmp_prev = prev;
Node *tmp_tail = cur;
int cnt = k;
while( cnt>0 ) {
tmp = cur->next;
cur->next = prev;
prev = cur;
cur = tmp;
cnt--;
if( !cur ) break;
}
if( !tmp_prev )
new_head = prev;
else
tmp_prev->next = prev;
tmp_tail->next = cur;
prev = tmp_tail;
}
head = new_head;
}
Node* reverseKnodes(Node *curnt, int k){
Node *temp = NULL;
Node *prev = NULL;
while(curnt != NULL && k > 0){
temp = curnt ->next;
curnt->next = prev;
prev = curnt;
curnt = temp;
k--;
}
temp = prev;
while(temp->next != NULL)
temp = temp->next;
temp->next = curnt;
curnt = prev;
return curnt;
}
Node* ReverseSpecial(Node *n, int k){
Node *head = n;
Node *tail = n;
int i = 0;
while(n != NULL && i < k){
n = n->next;
if(i < k - 1)
tail = tail->next;
i++;
}
if(n != NULL)
tail->next = ReverseSpecial(n, k);
head = reverseKnodes(head, k);
return head;
}
private LinkedListNode<T> Reverse(LinkedListNode<T> head, int k)
{
LinkedListNode<T> current = head;
LinkedListNode<T> last = null;
int i =0;
while(current != null)
{
i++;
if(i%k == 0)
{
head.Next = Reverse(current.Next, k);
break;
}
LinkedListNode<T> next = current.Next;
current.Next = last;
current = next;
}
return current;
}
private LinkedListNode<T> Reverse(LinkedListNode<T> head, int k)
{
LinkedListNode<T> current = head;
LinkedListNode<T> last = null;
int i =0;
while(current != null)
{
i++;
if(i%k == 0)
{
head.Next = Reverse(current.Next, k);
break;
}
LinkedListNode<T> next = current.Next;
current.Next = last;
current = next;
}
return current;
}
public Node reverse(Node head, int k) {
// after reverse, the return node is
// the last node in the first K nodes in the original list
// which is also the head node in the reversed list
Node returnNode = null;
// for the ith K sub list, the two "previous" pointers
// would point to the (i-1)th K sub list's head and tail "after" reverse
// This means, after reversing 3,2,1, previousTail points to 3 and previousHead points 1
Node previousTail = null;
Node previousHead = null;
while(head != null) { // not reached the end of the list
Node tail = head;
for(int i = 1; i < k & tail.next() != null; i ++) {
tail = tail.next();
}
Node nextHead = tail.next();
reverse(head, tail);
if( previousHead == null || previousTail == null) {
// first K sub list
previousHead = tail;
previousTail = head;
returnNode = tail;
} else
previousTail.setNext(tail);
head.setNext(nextHead);
head = nextHead;
}
return returnNode;
}
private Node reverse(Node current, Node tail) {
if(current == tail) {
return current;
}
Node next = reverse(current.next(), tail);
next.setNext(current);
return current;
}
public static Node reverseList (Node head, int k) {
Node ret_value = null;
int counter = 0;
Node previous = null;
Node headSequence = head;
while (head != null) {
counter++;
if ( counter <= k) {
Node next = head.next;
head.next = previous;
previous = head;
head = next;
} else {
counter = 0;
headSequence.next = head;
if ( !ret_value )
ret_value = previous;
previous = null;
}
}
return previous;
}
struct node * reverse(struct node *head)
{
struct node *p=(struct node *) malloc(sizeof(struct node));
struct node *q=(struct node *) malloc(sizeof(struct node));
struct node *temp=(struct node *) malloc(sizeof(struct node));
temp=head;
p=head->next;
head->next=NULL;
while(p!=NULL)
{
q=p->next;
p->next=head;
head=p;
p=q;
}
return temp;
}
void revert(struct node *head,int k)
{
int counter=0,found=0;
struct node *p=(struct node *) malloc(sizeof(struct node));
struct node *q=(struct node *) malloc(sizeof(struct node));
struct node *start=(struct node *) malloc(sizeof(struct node));
while(head!=NULL)
{
p=head;
while(counter++<k-1 && head!=NULL)
head=head->next;
if(head==NULL)
break;
q=head->next;
head->next=NULL;
if(found==0)
{
start=head;
found=1;
}
head=q;
while(--counter>0 && head!=NULL)
head=head->next;
if(head==NULL)
head=q;
reverse(p)->next=head;
counter=0;
head=q;
}
while(start != NULL)
{
printf("%d\t",start->val);
start = start->next;
}
printf("\n");
}
Here is the function that works with a LinkedList class that I implemented.
The reversal function implements tail-end recursion. Here it is:
- Killedsteel February 16, 2014