Microsoft Interview Question Software Engineer / Developers
the simpler the better ;)
list *kreverse(list *head, int k) {
if(k <= 1) // nothing to reverse
return head;
list *p = head, *tail = 0;
while(p != 0) {
// remember where we start this piece
list *start = p, *prev = 0, *temp;
int c = k;
while(p != 0 && c-- > 0) { // do usual reverse
temp = p->next;
p->next = prev;
prev = p;
p = temp;
}
if(tail != 0) // link reversed pieces
tail->next = prev;
else // indicates the first piece
head = prev;
tail = start;
// here p points to the next part being processed
}
return head;
}
my version:
two functions, one does normal reverse, the other does k reverse:
a helper function returns the length of the list
List* reverseList(List** head,int k)
{
List* prev=NULL;
List* next=NULL;
while(k>=1)
{ *head=current;
next=current->next;
current->next=prev;
prev=current;
current=next;
k--;
}
return *head;
}
List* KReverse(List** head, int k)
{
if(!head) return NULL;
List* current=*head;
if(!current) return NULL;
if(listlen(current))<k) return *head;
List knext=current;
while(k>1)
{
knext=knext->next;
k--;
}
*head=reverselist(current,k);
current->next=KReverse(knext,k);
}
int listLen(List* head)
{
int len=0;
if(!head) return 0;
while(head)
{
head=head->next;
len++;
}
return len;
}
reverse the linked list, start from the beginning of the reversed linked list break according to the k. if total length is n and n%k=r and r!=0 then break the linked list after r nodes.
definition of break: break the link after traversing k nodes and change the head of the linked list
O(n) and dealing with pointers will be easy!!!
After reversal:
11->10->(9->7)->(6->5->4)->(3->2->1)
(9->7)->11->10->(6->5->4)->(3->2->1)
(6->5->4)->(9->7)->11->10->(3->2->1)
(3->2->1)->(6->5->4)->(9->7)->11->10
<pre lang="c" line="1" title="CodeMonkey18259" class="run-this">#include <stdio.h>
struct node {
int data;
struct node *next;
};
typedef struct node *ListNode;
int count(ListNode head) {
if(head == NULL) return 0;
else return 1 + count(head->next);
}
void append(ListNode *head, int data) {
struct node *curr = NULL;
struct node *p = (struct node *) malloc(sizeof(struct node));
if(!p){
return;
}
p->data = data;
p->next = NULL;
if(*head == NULL){
*head = p;
return;
}
for(curr = *head; curr->next != NULL; curr = curr->next);
curr->next = p;
}
ListNode appendTest() {
struct node *head = NULL;
int i;
for(i = 0; i<100; i++) {
append(&head, i);
}
return head;
}
void printListReverse(ListNode t){
if(t==NULL)
return;
printListReverse(t->next);
printf("%d\n", t->data);
}
void printList(ListNode t){
if(t==NULL)
return;
printf("%d\n", t->data);
printList(t->next);
}
void delete(ListNode *headRef, int data){
ListNode prev = NULL;
ListNode curr = *headRef;
for(; curr != NULL; curr = curr->next){
if(curr->data == data){
ListNode tmp = curr;
if(prev){
prev->next = curr->next;
}
else{
*headRef = curr->next;
}
free(tmp);
}
prev = curr;
}
}
ListNode reverseHelp(ListNode head, int k, ListNode *firstRev){
ListNode t, x= head, r = NULL;
for(; k-- > 0; ){
t = x->next;
x->next = r;
r = x;
x = t;
}
*firstRev = r;
return x;
}
void reverseK(ListNode *headRef, int K)
{
int N = count(*headRef);
if(N<K){
return;
}
ListNode curr = *headRef;
ListNode prev = NULL;
ListNode currRev = NULL;
ListNode firstRev = NULL;
while(N-K >= 0){
currRev = reverseHelp(curr, K, &firstRev);
if(prev) {
prev->next = firstRev;
} else {
*headRef = firstRev;
}
prev = curr;
curr->next = currRev;
curr = currRev;
N = N-K;
}
if(N != 0 && prev){
prev->next = currRev;
}
}
int main(){
struct node *head = NULL;
head = appendTest();
//deleteR(&head, 9);
//reverseR(&head);
//reverse3(&head);
reverseK(&head, 10);
printList(head);
return 1;
}
</pre><pre title="CodeMonkey18259" input="yes">1
2
10
42
11
</pre>
<pre lang="c" line="1" title="CodeMonkey95211" class="run-this">HListNode intersect(ListNode first, ListNode second) {
int lengthFirst = count(first);
int lengthSecond = count(second);
ListNode largeList = lengthFirst >= lengthSecond ? first : second;
ListNode smallList = lengthFirst <= lengthSecond ? first : second;
int diff = lengthFirst - lengthSecond;
if(diff <0) diff = -diff;
while(diff-- > 0){
largeList = largeList->next;
}
ListNode commonNode = NULL;
while(largeList != NULL) {
if(largeList == smallList){
commonNode = largeList;
break;
}
largeList = largeList->next;
smallList = smallList->next;
}
return commonNode;
}
</pre><pre title="CodeMonkey95211" input="yes">1
2
10
42
11
</pre>
lnode* KReverse(lnode* head, int k)
{
if(k == 1)
return head;
if(!head)
return 0;
if(!head->nxt)
return head;
lnode* cur_prev = 0;
lnode* new_prev;
lnode* prev = 0;
lnode* cur = head;
lnode* nxt;
int n = 1;
while(cur)
{
nxt = cur->nxt;
if(n%k == 1)
{
new_prev = cur;
cur->nxt = 0;
}
else
{
cur->nxt = prev;
}
if(n%k == 0 || !nxt)
{
if(!cur_prev)
head = cur;
else
cur_prev->nxt = cur;
cur_prev = new_prev;
}
prev = cur;
cur = nxt;
n+=1;
}
return head;
}
Here is my code...Some optimization might be possible though...
- gauravk.18 April 14, 2008/* Reverse a Link list */ # include <stdio.h> # include <math.h> # include <stdlib.h> struct nodes { int value; struct nodes * next; }node; void sort(struct nodes * head); void reverse(struct nodes * head); void display_list(struct nodes *); struct nodes * make_linklist(int size); nodes* KReverse(nodes* head, int k); nodes * kreverse(nodes *head,int k); void main() { int num = 10,k = 0; struct nodes *head, *p; printf("Enter the value of k \n"); scanf("%d",&k); if(k < 0) { printf("Incorrect Input \n"); return; } head = make_linklist(num); p = head; //display_list(p); //printf("Now Reversing\n"); if(k) head = KReverse(head, k); //reverse(head); //sort(head); display_list(head); } nodes * KReverse(nodes* head, int k) { int n = k; nodes *new_next = head; nodes *new_head = head; while(n-- > 1) new_head = new_head->next; while(head) { n = k; int count = 0; while(n-- >0 && new_next->next != NULL) { new_next = new_next->next; count++; } if(count < k) new_next = NULL; kreverse(head, k); n = k; nodes * temp = new_next; while(n-- > 1 && temp != NULL && temp->next != NULL) temp = temp->next; head->next = temp; head = new_next; } return new_head; } nodes * kreverse(nodes * head, int k) { int n = k-1; nodes * tail = head; while(n-- > 0 && tail->next != NULL) tail = tail->next; tail->next = NULL; reverse(head); return head; } void reverse(struct nodes *head) { struct nodes *prev, *now, *future; prev = head; now = prev->next; while(now) { future = now->next; now->next = prev; prev = now; now = future; } head->next = NULL; head = prev; //display_list(head); } struct nodes * make_linklist(int size) { struct nodes *prev, *now, *head; head = (struct nodes*) malloc(sizeof(nodes)); head->value = 100; prev = head; for(int i=0;i<size-1;i++) { now = (struct nodes*) malloc(sizeof(nodes)); now->value = i; prev->next = now; prev = now; } now->next = NULL; return head; } void display_list(struct nodes * p) { while(p) { printf("The element is %d \n",p->value); p = p->next; } }