Amazon Interview Question
Country: United States
public void kreverse(int k) {
SingleLLNode prev = null;
SingleLLNode temp = this.next;
int count=0;
SingleLLNode header = this;
while(temp!= null) {
header.next = temp;
temp =temp.next;
header.next.next = prev;
prev = header.next;
count++;
if (count == k) {
while(count > 0) {
header = header.next;
count--;
}
prev = null;
}
}
}
If the list is 1->2->3->4 and k=2; the above code gives:
1->3->2->4. I thought as per the question, it should have been: 2->1->4->3
/* This function prints all nodes that are distance k from a leaf node
path[] --> Store ancestors of a node
visited[] --> Stores true if a node is printed as output. A node may be k
distance away from many leaves, we want to print it once */
void kDistantFromLeafUtil(Node* node, int path[], bool visited[],
int pathLen, int k)
{
// Base case
if (node==NULL) return;
/* append this Node to the path array */
path[pathLen] = node->key;
visited[pathLen] = false;
pathLen++;
/* it's a leaf, so print the ancestor at distance k only
if the ancestor is not already printed */
if (node->left == NULL && node->right == NULL &&
pathLen-k-1 >= 0 && visited[pathLen-k-1] == false)
{
cout << path[pathLen-k-1] << " ";
visited[pathLen-k-1] = true;
return;
}
/* If not leaf node, recur for left and right subtrees */
kDistantFromLeafUtil(node->left, path, visited, pathLen, k);
kDistantFromLeafUtil(node->right, path, visited, pathLen, k);
}
/* Given a binary tree and a nuber k, print all nodes that are k
distant from a leaf*/
void printKDistantfromLeaf(Node* node, int k)
{
int path[MAX_HEIGHT];
bool visited[MAX_HEIGHT] = {false};
kDistantFromLeafUtil(node, path, visited, 0, k);
}
public class Solution {
public static void reverseKNodesLinkedList(List<Integer> list, int k) {
int len = list.size();
int i = 0;
int k1 = 0;
int kTemp = 0;
while ( i + k <= len) {
k1 = i + k - 1;
kTemp = i + k;
while (i < kTemp && i < k1) {
Integer temp = list.get(i);
list.set(i, list.get(k1));
list.set(k1, temp);
i++;
k1--;
}
if (i < kTemp) {
i = kTemp;
}
}
}
public static void main(String[] args) {
List<Integer> list = new LinkedList<Integer>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
reverseKNodesLinkedList(list, 5);
Iterator<Integer> iter = list.iterator();
while (iter.hasNext()) {
System.out.print(iter.next() + ",");
}
}
}
/**
*
*/
package linkedlist;
import linkedlist.LinkedList;
import linkedlist.Node;
public class ReverseKLL {
/**
* @param args
*/
Node reverseKLL ( int k , Node head ) {
if ( head == null )
return head;
if ( k == 0 )
return head;
Node t = null;
Node tNext = null;
if ( head != null )
t = head.getNext();
if ( t != null )
tNext = t.getNext();
int k1 = k;
Node headNew = head;
Node tNew = t;
Node tNextNew = tNext;
boolean terminated = false;
while ( k1 > 1 && tNew != null ) {
tNew.setNext(headNew);
headNew = tNew;
tNew = tNextNew;
if ( tNextNew != null )
tNextNew = tNextNew.getNext();
k1--;
}
if ( tNew == null )
terminated = true;
if ( terminated )
head.setNext(null);
t = tNew;
if ( t != null )
head.setNext(reverseKLL(k,t));
return headNew;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Object[] a = {1,2,3,4,5,6,7};
int k = 4;
LinkedList ll = new LinkedList (a);
Node head = ll.getLL();
ReverseKLL o = new ReverseKLL();
head = o.reverseKLL(k, head);
ll.display(head);
}
}
O(n/2):O(1) time:space
public static void main(String[] args) {
// TODO Auto-generated method stub
LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
reverseKNodes(list, 5);
for (Integer i : list)
System.out.println(i);
}
public static void reverseKNodes(LinkedList<Integer> list, int k){
int i,j;
int loop = list.size() / k;
while (loop != 0){
j = loop * k - 1;
i = j + 1 - k;
while (j > i){
int temp = list.get(j);
list.set(j, list.get(i));
list.set(i, temp);
j--;
i++ ;
}
loop--;
}
}
public static void kReverse(Node * st, int k){
Node *p, *s1, e1;
int i;
if(k<2)
return;
p = null;
s1 = e1= st;
while(s1!=null){
for(i=0; i< k-1 || e1 != null; i++, e1= e1->nxt);
reverseList(s1,e1);
if(p==null)
st = s1;
p = e1;
s1 = p->nxt;
e1 = s1;
}
}
public static void reverseList( Node * start, Node * end){
Node *p, *q;
p = start;
while(start != end){
q = start -> nxt;
start -> nxt = end -> nxt;
end -> nxt = start;
start = q;
}
end = p;
}
#include <stdio.h>
#include <string.h>
struct list *newnode(int data);
int count1=1;
struct list
{
int data;
struct list *next;
}*p,*p1,*p3,*p4;
main()
{
struct list *root1;
struct list *root=newnode(1);
root->next=newnode(2);
root->next->next=newnode(3);
root->next->next->next=newnode(4);
root->next->next->next->next=newnode(5);
root->next->next->next->next->next=newnode(6);
root->next->next->next->next->next->next=newnode(7);
root->next->next->next->next->next->next->next=newnode(8);
printf(" Before Doing Swapping ");
printf("\n");
linkedlist(root);
printf("\n");
int count =no_nodes(root);
root1=root;
do_swap(root,root1,count,3);
printf(" After Doing Swapping ");
printf("\n");
linkedlist(root);
printf("\n");
}
void linkedlist(struct list *tree)
{
while(tree!=NULL)
{
printf(" %d",tree->data);
tree=tree->next;
}
}
void do_swap(struct list *root,struct list *root1,int count,int n)
{
int count1=count-n;
int i=1;
int j1=1;
if(count1==n)
{
printf(" Cannot Be Done ");
exit(0);
}
if(n>count)
{
printf(" Larger Size Cannot Be Done ");
exit(0);
}
while(i<=n-1)
{
if(i==n-1)
{
p=root->next;
p1=root->next->next;
i++;
}
else
{
root=root->next;
i++;
}
}
while(j1<=count1)
{
if(j1==count1)
{
p3=root1->next;
p4=root1->next->next;
j1++;
}
else
{
root1=root1->next;
j1++;
}
}
root->next->next=NULL;
root->next=NULL;
root1->next->next=NULL;
root1->next=NULL;
root->next=p3;
p3->next=p1;
root1->next=p;
p->next=p4;
}
int no_nodes(struct list *tree2)
{
while(tree2!=NULL)
{
count1++;
tree2=tree2->next;
}
return count1-1;
}
struct list *newnode(int data)
{
struct list *tree1=(struct list *)malloc(sizeof(struct list));
tree1->data=data;
tree1->next=NULL;
return tree1;
}
public Node reverse(Node start, int k){
Node prev = null;
Node current = start;
Node next = null ;
int count = 0;
while (current != null && count <k) {
next = current.next;
current.next = prev;
prev = current;
current = next;
count++;
}
if(next != null){
start.next = reverse(next, k);
}
return prev;
}
3 pointers, p, p->next, p->next->next, do the reverse, then repeat...
- Anonymous February 16, 2014