Amazon Interview Question
SDE-2sCountry: India
Interview Type: Written Test
struct listNode
{
int data;
listNode *next;
listNode(int val) :data(val), next(NULL){}
};
listNode * createLinkedList(int numberOfNodes)
{
listNode *head = new listNode(1);
int i = 2;
listNode *p = head;
while (i <= numberOfNodes)
{
p->next = new listNode(i);
p = p->next;
i++;
}
return head;
}
void printLinkedList(listNode *head)
{
while (head != NULL)
cout << head->data << ", ", head = head->next;
cout << endl;
}
listNode * reverseFirstKNodes(listNode *head, int k)
{
if (head == NULL || head->next == NULL)
return head;
listNode *p = head;
listNode *q = head->next;
while (k > 1 && q != NULL)
{
listNode *r = q->next;
q->next = p;
k--;
p = q;
q = r;
}
head->next = q;
return p;
}
void reverseKAlternateNodes(listNode *&head, int k)
{
if (k < 2 || head == NULL || head->next == NULL)
return;
listNode *p = head;
listNode *tail = NULL;
head = NULL;
while (p != NULL)
{
if (head == NULL)
{
head = reverseFirstKNodes(p, k);
p = head;
}
else
{
tail->next = reverseFirstKNodes(p, k);
p = tail->next;
}
// skip 2*k -1 nodes
int i = 2 * k - 1;
while (i > 0 && p != NULL)
{
p = p->next;
i--;
}
if (p != NULL)
{
tail = p;
p = p->next;
}
}
}
int main()
{
listNode *head = createLinkedList(11);
reverseKAlternateNodes(head, 3);
printLinkedList(head);
// free list head
getchar();
return 0;
}
Node reverseKAlt(Node head, int k){
if(head == null ) return head;
Node p = head;
Node q = head->next;
p->next = null;
while(q!= null){
var r = q->next;
p = q;
if( (k/3) % 2 != 0)
q->next = p;
q = r
}
return p;
}
c# implementation.
using System;
namespace SinglyLinkedListReverse {
class Program {
private static void ReverseAltKNodes<T>( ref Node<T> headNode, int k ) {
int i = -1;
var arr = new Node<T>[ k ];
var currNode = headNode;
Node<T> prevNodeBeforeGroup = null;
while ( currNode != null ) {
i++;
if ( i <= k*2 - 1 && i >= k) {
prevNodeBeforeGroup = currNode;
currNode = currNode.NextNode;
i = ( i == k * 2 - 1 ) ? -1 : i;
continue;
}
arr[ i ] = currNode;
if ( currNode.NextNode != null && i < k - 1 ) {
currNode = currNode.NextNode;
continue;
}
var nextNode = currNode.NextNode;
for ( int j = i; j > 0; j-- ){
arr[ j ].NextNode = arr[ j - 1 ];
}
arr[ 0 ].NextNode = nextNode;
if ( prevNodeBeforeGroup == null )
{ headNode = currNode; }
else { prevNodeBeforeGroup.NextNode = currNode; }
currNode = nextNode;
prevNodeBeforeGroup = arr[ 0 ];
arr = new Node<T>[ k ];
}
}
private const int limit = 18;
private static Node<int> CreateSinglyLinkedList( int n = 1 ) {
var node = new Node<int> { Data = n };
if ( n < limit ) {
node.NextNode = CreateSinglyLinkedList( ++n );
}
return node;
}
public class Node<T> {
public T Data { get; set; }
public Node<T> NextNode { get; set; }
}
static void Main(string[] args) {
var headNode = CreateSinglyLinkedList();
ReverseAltKNodes( ref headNode, 4 );
var currNode = headNode;
while ( currNode != null ) {
Console.WriteLine( currNode.Data );
currNode = currNode.NextNode;
}
Console.ReadLine();
}
}
}
#include <stdlib.h>
#include <iostream>
using namespace std;
// to reverse the linkedlist, I will use recursion to the end/right of the list, reverse the last k nodes there, return its new head, and link the last reversed list to the left side list. and operate on the section with k nodes, and then on next left k nodes... until reach the head
struct ListNode{
int value;
ListNode* next;
ListNode(int v) : value(v), next(NULL){}
};
ListNode* reverseKNodes(ListNode* head, int k, int sec){
// find the head of the next section (k nodes)
ListNode* curr = head;
for(int i = 0; i < k; i++){
if(curr == NULL){
return head;
}
curr = curr->next;
}
ListNode* end = head;
for(int i = 0; i < k - 1; i++){
end = end->next;
}
ListNode* next = curr; // head of the next section
// reverse the this section (k nodes) only if this is an odd section
if(sec % 2 == 1){
ListNode *prev = NULL;
curr = head;
for(int i = 0; i < k; i++){
ListNode* t = curr->next;
curr->next = prev;
prev = curr;
curr = t;
}
head->next = reverseKNodes(next, k, sec + 1); // link to the next section
// the new head of this section is prev
return prev;
}
else{
end->next = reverseKNodes(next, k, sec + 1);
return head;
}
}
ListNode* reverse(ListNode* head, int k){
return reverseKNodes(head, k, 1);
}
int main(){
ListNode* head = new ListNode(0);
ListNode* curr = head;
for(int i = 0; i < 21; i++){
curr->next = new ListNode(i+1);
curr = curr->next;
}
ListNode* result = reverse(head, 5);
cout << "******************" << endl;
while(result != NULL){
cout << result->value << " ";
result = result->next;
}
cout << endl;
return 0;
}
What I understood is to reverse the first K nodes in the case of alternative we need to navigate ti the staring node.
Note. I dont have a compiler but is the idea.
public class ListNode
{
int Data;
ListNode Next;
}
public ReverseFirstKNodes(ListNode list, int k)
{
if (list == null)
return null;
ListNode root = new ListNode();
ListNode p = list;
ListNode last = list;
int i = 0;
while (i < k && p != null)
{
ListNode q = p.Next;
p.Next = root.Next;
root.Next = p;
p = q;
i++;
}
last.Next = p;
return root.Next;
}
in O(n), read the linked list in reverse order
public String getKElementsReverse(int n, int k){
String ret = ",";
boolean extra = false;
int seek= 0;
while((seek + k) <= n){
seek += k;
if(seek != n){
seek++;
extra = true;
}
else{
extra = false;
}
}
if(extra){
seek--;
}
Node temp = this;
for(int i= seek; i<=n; i++){
temp = temp.prev;
}
while(temp != null){
//temp = temp.prev;
for(int i=k; i>0; i--){
ret += temp.getContent() + ",";
temp = temp.prev;
}
if(temp != null){
temp = temp.prev;
}
ret += ";";
}
return ret;
}
then display nodes from front, with blocks of size k extracted from the end of "ret"
static String printKPartsReversed(Node temp, String[] kParts, int n, int k){
//temp= temp.getNext();
String full = "";
int count = 0;
int seek = 0;
int l = kParts.length;
while(seek < n){
full += kParts[l -1 - count++];
for(int i=0; i<k; i++){
temp = temp.getNext();
}
if(temp.getNext() == null){
//indicates tail reached
break;
}
seek += k+1;
full += temp.getContent() + ", ";
temp = temp.getNext();
}
return full;
}
Overall time complexity= O(n)
tests on cases that i considered ... but test it no your input before using
O(N) time and O(N) space. Solution written in C#:
public static void Reverse (ref Node root, int number)
{
if (number < 0)
throw new ArgumentOutOfRangeException("number");
Stack<Node> reversedNodes = new Stack<Node>();
Node iteratingNode = root;
for (int cnt = 0; cnt < number && iteratingNode != null; iteratingNode = iteratingNode.Next, cnt++ ) {
reversedNodes.Push(iteratingNode);
}
var linkWith = iteratingNode;
Node previous = null;
for (; reversedNodes.Count > 0;)
{
var node = reversedNodes.Pop();
if (previous == null)
root = node;
else
previous.Next = node;
previous = node;
}
if (previous != null)
previous.Next = linkWith;
}
node* reverseListAlt(node *record, int k)
{
int count= 0;
node* head, *prev;
node* first= record;
node* last= record;
if (k<0)
head= record;
else if(k==0)
head= reverseList(first, NULL);
else
{
//reverse first k nodes
while(count < k && last!= NULL)
{
last= last->next;
count++;
}
head= reverseList(first, last);
// Reverse Alternate k nodes
while(last != NULL)
{
//Skip k ndoes
while(count > 0 && last!=NULL)
{
prev= last;
last= last->next;
count--;
}
//Reverse K nodes
first= last;
while(count < k && last!=NULL)
{
last= last->next;
count++;
}
prev->next= reverseList(first, last);
}
}
return head;
}
node* reverseListAlt(node *record, int k)
{
int count= 0;
node* head, *prev;
node* first= record;
node* last= record;
if (k<0)
head= record;
else if(k==0)
head= reverseList(first, NULL);
else
{
//reverse first k nodes
while(count < k && last!= NULL)
{
last= last->next;
count++;
}
head= reverseList(first, last);
// Reverse Alternate k nodes
while(last != NULL)
{
//Skip k ndoes
while(count > 0 && last!=NULL)
{
prev= last;
last= last->next;
count--;
}
//Reverse K nodes
first= last;
while(count < k && last!=NULL)
{
last= last->next;
count++;
}
prev->next= reverseList(first, last);
}
}
return head;
}
Here is the function. Well tested.
node* reverseList(node *head, node* last)
{
node* prev= last;
node* cur=head;
node* next;
if (head == NULL)
return NULL;
while(cur != last)
{
next= cur->next;
cur->next= prev;
prev= cur;
cur= next;
}
return prev;
}
node* reverseListAlt(node *record, int k)
{
int count= 0;
node* head, *prev;
node* first= record;
node* last= record;
if (k<0)
head= record;
else if(k==0)
head= reverseList(first, NULL);
else
{
//reverse first k nodes
while(count < k && last!= NULL)
{
last= last->next;
count++;
}
head= reverseList(first, last);
// Reverse Alternate k nodes
while(last != NULL)
{
//Skip k ndoes
while(count > 0 && last!=NULL)
{
prev= last;
last= last->next;
count--;
}
//Reverse K nodes
first= last;
while(count < k && last!=NULL)
{
last= last->next;
count++;
}
prev->next= reverseList(first, last);
}
}
return head;
}
1. Traverse k nodes forward and set temp to the k+1th node
- r.s December 16, 20152. Reverse k nodes traversed in step 1.
3. Set next of the last node in this k length list to temp.
4. Traverse next k nodes which are to be skipped.
5. Recursively call steps 1-3 for reversing next k nodes.
Code and Credits: IDeserve (Reverse every alternate k nodes of a Linked List)