CareerCup

Can you elaborate what do you mean by reversing every k nodes of LL?

I think this Code will work
struct node *reverse (struct node *head, int k)
{
struct node* current = head;
struct node* next;
struct node* prev = NULL;
int count = 0;

/*reverse first k nodes of the linked list */
while (current != NULL && count < k)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
count++;
}

if(next != NULL)
{ head->next = reverse(next, k); }

/* prev is new head of the input list */
return prev;
}

void reverseList(Node** root) {
  Node* prev = 0;
  while (*root) {
    Node* temp = (*root) -> next;
    (*root) -> next = prev;
    prev = *root;
    *root = temp;
  }
  *root = prev;
}

/* Reverse of every K  nodes in Single Linked list */

void  reverse(node * head, node ** end1, node **end2, int n, int K)
{
    if( head == NUL)
    {
        return NULL;
    }
    else if( head->next  == NULL)
    {
        *end1 = NULL;
    }
    else
    {
        reverse(head, end1, end2, n+1, K);
        if( n%K == 0)
        {
            head->next->next = head;
            head->next = end2;
            end2 = end1;
        }
        else if( n% K == K-1)
        {
            end1 = head;
        }
        else
        {
            head->next->next = head;
        }
    }

}

node * Reverse_K_nodes(node *head, int K)
{
    node *end1=NULL,*end2=NULL;
    reverse(head, &end1, &end2, 0, K)
    return end2;

}

int main()
{
    head = Reverse_K_nodes(head, K );
}

Time Complexity O(n) & Space complexity O(1).

If you find any bug please let me know.

why the hell do u put code?? put the algo! code everyone can write..not the algo..such posts are just a waste of time

I think this siva sai is a chutface randi Son of a Bit__ ;)

Algo is pretty simple.
Maintain a stack s, two pointers p1, p2. Let the list be l and first node be l->start.
p1 points to the next node to be processed
p2 points to end of new list with nodes in desired order (K-reversed)
As we traverse the list, we push the nodes onto stack, after every K-steps, we pop the stack (till it gets empty) and add to the end of p2.
Here's code for same (function reverseK):

#include <stdio.h>

// List node with int as payload
struct lnode {
    int data;
    struct lnode *next;
};

struct lnode *newLNode(int data, struct lnode *next) {
    struct lnode *node = (struct lnode *) malloc(sizeof(struct lnode));
    node->data = data;
    node->next = next;
    return node;
}

// List node
typedef struct {
    struct lnode *start;
} List;

List *newList() {
    List *l = (List *) malloc(sizeof(List));
    l->start = NULL;
    return l;
}

// Stack node
struct snode {
    void *data;
    struct snode *next;
};

struct snode *newSNode(void *data, struct snode *next) {
    struct snode *node = (struct snode *) malloc(sizeof(struct snode));
    node->data = data;
    node->next = next;
    return node;
}

// Stack
typedef struct {
    struct snode *top;
} Stack;

Stack *newStack() {
    Stack *s = (Stack *) malloc(sizeof(Stack));
    s->top = NULL;
    return s;
}

void push(Stack *s, void *data) {
    struct snode *node = newSNode(data, s->top);
    s->top = node;
}

void *pop(Stack *s) {
    void *data;
    struct snode *node = s->top;
    if(node == NULL)
        return;
    s->top = node->next;
    data = node->data;
    free(node);
    return data;
}

int isEmpty(Stack *s) {
    return (s->top == NULL);
}

void printList(List *l) {
    struct lnode *node = l->start;
    
    while(node!=NULL) {
        printf("%2d   ", node->data);
        node = node->next;
    }
    printf("\n");
}

// Reverse in steps of K elements
void reverseK(List *l, int k) {
    Stack *s = newStack();
    int i;
    struct lnode *p1, *p2;
    
    // To maintain l->start, do it separately for first K-elements
    for(i=0, p1=l->start; i<k && p1!=NULL; i++, p1=p1->next)
        push(s, p1);
    p2 = l->start = (struct lnode *) pop(s);
    // empty list
    if(l->start == NULL)
        return;
    while(!isEmpty(s)) {
        p2->next = (struct lnode *) pop(s);
        p2 = p2->next;
    }
    // Now do it for remaining elements 0..k-1, k...2k-1,...
    for(i=0; p1!=NULL; i++, p1=p1->next) {
        if(i%k==0) {
            while(!isEmpty(s)) {
                p2->next = (struct lnode *) pop(s);
                p2 = p2->next;
            }
        }
        push(s, p1);
    }
    // lastly for elements left in stack
    while(!isEmpty(s)) {
        p2->next = (struct lnode *) pop(s);
        p2 = p2->next;
    }
    // avoid loops
    p2->next = NULL;
}

List *buildList() {
    List *l = newList();
    l->start = newLNode(1, NULL);
    l->start->next = newLNode(2, NULL);
    l->start->next->next = newLNode(3, NULL);
    l->start->next->next->next = newLNode(4, NULL);
    l->start->next->next->next->next = newLNode(5, NULL);
    l->start->next->next->next->next->next = newLNode(6, NULL);
    l->start->next->next->next->next->next->next = newLNode(7, NULL);
    l->start->next->next->next->next->next->next->next = newLNode(8, NULL);
    l->start->next->next->next->next->next->next->next->next = newLNode(9, NULL);
    l->start->next->next->next->next->next->next->next->next->next = newLNode(10, NULL);
    l->start->next->next->next->next->next->next->next->next->next->next = newLNode(11, NULL);
    l->start->next->next->next->next->next->next->next->next->next->next->next = newLNode(12, NULL);  
    return l;  
}

int main() {
    List *l = buildList();
    
    printList(l);
    reverseK(l, 3);
    printList(l);
    
    return 0;
}

list* reverseList(list* head){
list* temp = NULL, prev = NULL;

while(head){
 temp = head->next;
 head->next = prev;
 prev = head;
 head = temp;
 }

return prev;

P.S. In order to implement for every K,

Stop the While Loop at K and Reitirate the enitre while for n/K where n is lenght of list.