CareerCup

// inside some linked list implementation
    public MyListNode reverseK(MyListNode head, int k) {

        // reversed the first k node, store 1. new head node 2. new tail node 3. original k + 1 node
        // call reverseK recursively on the [k + 1 node] as head
        // connect [new tail node] to the head of the recursion result
        // return [new head node]

        if (head == null)
            return null;

        if (k <= 1)
            return head;

        MyListNode new_head = head;
        MyListNode new_tail = head;
        MyListNode k_next = null;

        MyListNode p1 = head;
        MyListNode p2 = head.next; // NOT OOP, for simplicity

        for (int n = 1; n < k && p2 != null; n++) {
            MyListNode p2_next = p2.next;

            p2.next = p1;

            // advance p1, p2 by one
            p1 = p2;
            p2 = p2_next;

            // when hit the k-th node, or the end of list
            if (n == k-1 || p2 == null) {
                new_head = p1;
                k_next = p2;
            }
        }

        MyListNode k_next_head = reverseK(k_next, k);

        // connect lists
        new_tail.next = k_next_head;

        return new_head;
    }

    public MyLinkedList reverseListK(int k) {
        head = reverseK(head, k);
        return this;
    }

public static Node kReverseList(int k, Node head) {
		int i = 0;
		Node x = head;
		if (x == null) {
			
		}
		Node y = x.next;
		if (y == null)
			return x;
		Node z = x.next.next;
		while (i < k - 1) {
			y.next = x;
			if (z == null) {
				head.next = null;
				return y;
			}
			x = y;
			y = z;
			z = z.next;
			i++;
		}
		head.next = kReverseList(k, y);
		return x;
	}

public static MyNode reverselist(MyNode list, int k)
        {
            if (list == null) return list;
            if (k <= 0) return list;

            MyNode head = list;
            int k1 = k;
            k--;
            while (list.next != null && k > 0)
            {
                MyNode tmp1 = head;
                head = list.next;
                MyNode tmp = head.next;
                head.next = tmp1;
                
                list.next = tmp;
                k--;
            }
            if (k > 0) return null;
            list.next = reverselist(list.next, k1);
            return head;
        }

This solution assumes that you have a class called SinglyLinkedList which has a private variable as "Node head". and a method called createSampleList() which return a singly linked list with some numbers added in to it.
Whatever parameter you will give which calling the reverseKElement is 'k'.
So its generic solution.
so assume main method from some class:
--------------------------------------------------------------------------------------------
public static void main(String[] args){
SinglyLinkedList sll = new SinglyLinkedList().createSampleList();
sll.reverseKElements(1);
---------------------------------------------------------------------------------------------
public void reverseKElements(int k){
head=reverseKElements(head, k);
}

private Node reverseKElements(Node head, int k){
System.out.println("Start:-------------------------------------------");
if(head==null)
return null;

int totalElementsToBeReversedByMe;

Node myLastNode = head;

//mark our boundary.
// totalElementsToBeReversedByMe is initialised to 1, since already head is counted.
for( totalElementsToBeReversedByMe=1 ; totalElementsToBeReversedByMe < k; totalElementsToBeReversedByMe++){
if(myLastNode.getNextNode() != null){
myLastNode = myLastNode.getNextNode();
}
else{
break;
}
}

System.out.println("Total elements with me:"+totalElementsToBeReversedByMe);
System.out.println("My head is:"+head.getData());
if(myLastNode!=null){
System.out.println("My tail node is:"+myLastNode.getData());
}
else{
System.out.println("My tail node is null");
}

Node myNextListsHead = null;
// currently I have pointers to my head and my tail of K elements
if(myLastNode.getNextNode() != null){
myNextListsHead = reverseKElements(myLastNode.getNextNode(), k);
}

if(myNextListsHead != null)
System.out.println("My Next Lists Head is:"+myNextListsHead.getData());
else
System.out.println("My Next List head is null.... means I am the last part of the list");

//reverse my boundry of linked list
Node myNewHead = reverseMyBoundryOfLinkedList(head, myLastNode.getNextNode(), totalElementsToBeReversedByMe);

// set my tail to my childs head...
// now my earlier head should have been converted to the tail
if(head.getNextNode() !=null) head.setNextNode(myNextListsHead);

if(myNextListsHead!=null && head!=null)
System.out.println("Setting my new tails ("+head.getData()+") next to my nextList head ("+myNextListsHead.getData()+")");
else
System.out.println("There is nobody at my end.. m the last part of the list...");

System.out.println("End:-------------------------------------------");

return myNewHead;
}

private Node reverseMyBoundryOfLinkedList(Node myHead, Node myTailsNext, int totalElementsToBeReversed ) {
// p represents newHead
Node p = null, q = null, r = null;

if(myHead.getNextNode()==null)
return myHead;

p = myHead;
q = p.getNextNode();

for(int i=0; i < (totalElementsToBeReversed-1); i++){
r = q.getNextNode();
q.setNextNode(p);
p = q;
q = r;
}

//head has become tail now, and the next element should be myTailsNext
myHead.setNextNode(myTailsNext);

//return newHead
return p;
}

is temporary buffer allowed?
I was thinking of a non recursive solution:

Node* reverseK(Node* h, int k)
{
	if(h==NULL)
		return NULL;
	if(k<=1)
		return h;
	stack<int> nstack;
	Node* h1=NULL;
	Node* curr=NULL;
	int counter=0;
	while(h!=NULL)
	{
		nstack.push(h->value);
		h=h->next;
		counter++;
		if(counter==k)
		{
			while(counter>0)
			{
				int temp=nstack.top();
				nstack.pop();
				counter--;
				if(h1==NULL)
				{
				    h1=new Node();
					h1->value=temp;
					curr=h1;
				}
				else
				{
					Node* n=new Node();
					n->value=temp;
					curr->next=n;
					curr=n;
				}
			}
		}
	}
	if(curr!=NULL)
		curr->next=NULL;
	return h1;
}

that works for all my test cases, and the time is O(n), just not sure if the temporary stack and new list is ok?

O(n)

#include <iostream>

using namespace std;

struct Node {
    int value;
    Node* next;

    Node(int value): value(value) {}
};

Node* mkNode(const int& x, Node* after) {
    Node* newNode = new Node(x);
    newNode->next = after;
    return newNode;
}

Node* rev_first_few(Node* head, int few) {
    if (head == 0) return 0;
    Node *current = head;
    int i = 0;
    while(++i < few) {
        Node* next = head->next;
        if (next == 0) break;
        Node* next_2_next = next->next;
        next->next = current;
        head->next = next_2_next;
        current = next;
    }
    head->next = rev_first_few(head->next, few);
    return current;
}

int main(int argc, char** argv) {
    Node* head = mkNode(1, mkNode(2, mkNode(3, mkNode(4, mkNode(5, mkNode(6, mkNode(7, mkNode(8, 0))))))));
    head = rev_first_few(head, 3);
    while(head != 0) {
        cout << head->value << " ";
        Node* next = head->next;
        delete head;
        head = next;
    }
    cout << endl;
    return 0;
}

void reverse(int n,int len) //to reverse last 'n' elements of a linked list, len=length of list
{
if(n==0||n==1) //no elements to be reversed or only 1 element
{
cout<<"No change in the list!"<<endl;
return;
}
else if(n>len)
{
cout<<"More than number of elements!"<<endl;
return;
}
else
{
node*p=L;
node*q=NULL;
node*s;
node*r=NULL;
int i=1;
while(i!=(len-n)&&len!=n)
{
p=p->next;
i++;
}
if(p->next!=NULL&&p!=L)
q=p->next;
else
q=L;
while(q!=NULL)
{
s=r;
r=q;
q=q->next;
r->next=s;
}
if(n==len) //entire list is reversed,so adjust head node
L=r;
else
p->next=r;
}
}

#include <iostream>

using namespace std;

struct node{
node* next;
int data;
};

struct retnode
{
node* first;
node* nextnode;
};

class list
{
public:
node* head;
list();
void insert_front(int x);
int head_val();

//void delete_front(int x);
//node* delete_node(node* x);
};

int list::head_val()
{
	return head->data;
}

void list::insert_front(int x)
{
	if (!(head->data))
	{
		head->data=x;
	}
	else
	{
		node* a=new node();
		a->data=x;
		a->next=head;
		head=a;
	}
}

list::list()
{
	head=new node();
	head->data=NULL;
	head->next=NULL;
}

retnode* reversek(node* hed, int k)
{
	retnode* abc=new retnode();
	abc->first=NULL;
	abc->nextnode=NULL;
	if (hed==NULL){return abc;}
	else if (hed->next==NULL)
	{	abc->first=hed;
		return abc;
	}
	else{
		node* a=hed;
		node* b=a->next;
		node* c=b->next;
		while (b!=NULL && k>1)
		{	
			k--;
			b->next=a;
			if (c==NULL)
			{
				abc->first=b;
				return abc;
			}
			else
			{
				a=b;
				b=c;
				c=c->next;
			}
		}
		abc->first=a;
		abc->nextnode=b;
		return abc;
	}
}

void reversedk(list* l, int n)
{
	node* old_head=l->head;
	retnode* k=reversek(old_head,n);
	//old_head->next=k->nextnode;
	l->head=k->first;
	//old_head=k->nextnode;
	node* newnode=k->nextnode;
	while (k->nextnode!=NULL)
	{
		k=reversek(k->nextnode,n);
		//cout<<endl<<"--------";
		old_head->next=k->first;
		old_head=newnode;
		newnode=k->nextnode;
	}
	
}


int main()
{
	cout<< "hi";
	list l1;
	l1.insert_front(1);
	l1.insert_front(2);
	l1.insert_front(3);
	l1.insert_front(4);
	l1.insert_front(5);
	//retnode* k=reversek(l1.head,2);
	//cout<<"  "<<k->first->data<<"  "<<k->nextnode->data;
	//l1.head->next=reversek(l1.head,2);
	//l1.head=k->first;
	reversedk(&l1,3);
	cout<<"  "<<l1.head_val();
	cout<<"  "<<l1.head->next->data;
	cout<<"  "<<l1.head->next->next->data;
	cout<<"  "<<l1.head->next->next->next->data;
	cout<<"  "<<l1.head->next->next->next->next->data;
	
}

struct list{
int data;
struct list*next;
}*start;


struct list* IterativeReverse(int k)
{
struct list*cur=NULL, *ptr1=NULL, *ptr2=NULL;
cur=start;
if(start->next)
ptr1=cur->next;
else //if linked list contains only one node.
return start;
ptr2=ptr1->next;//can be NULL in the beginning itself.

struct list*temp=cur;
k=k-1;
while(--k)//loop shud iterate <=k-2 times
{
ptr1->next=cur;
cur=ptr1;
ptr1=ptr2;
ptr2=ptr2->next;
if(!ptr2) break; //if k exceeds its no of nodes.
}
ptr1->next=cur;
temp->next=ptr2;
start=ptr1;
return ptr1;
}

call the function IterativeReverse as
start=IterativeReverse(k);

#include<stdio.h>
#include<stdlib.h>
 
/* Link list node */
struct node{
    int data;
    struct node* next;
};

/* Function to reverse the linked list */
static void reverse(struct node** head_ref)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    while (current != NULL)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
    }
    *head_ref = prev;
}

/* Function to reverse first K nodes in the linked list */
static void reverseK(struct node** head_ref, int k)
{
    struct node* prev   = NULL;
    struct node* current = *head_ref;
    struct node* next;
    struct node* temp   = *head_ref;
    while (current != NULL && k>0)
    {
        next  = current->next;  
        current->next = prev;   
        prev = current;
        current = next;
        k--;
    }
    temp->next = current;
    *head_ref = prev;
}

 
/* Function to push a node */
void push(struct node** head_ref, int new_data)
{
    /* allocate node */
    struct node* new_node =
            (struct node*) malloc(sizeof(struct node));
            
    /* put in the data  */
    new_node->data  = new_data;
                
    /* link the old list off the new node */
    new_node->next = (*head_ref);    
        
    /* move the head to point to the new node */
    (*head_ref)    = new_node;
}
 
/* Function to print linked list */
void printList(struct node *head)
{
    struct node *temp = head;
    while(temp != NULL)
    {
        printf("%d  ", temp->data);    
        temp = temp->next;  
    }
}    
 
/* Drier program to test above function*/
int main()
{
    /* Start with the empty list */
    struct node* head = NULL;
   
     push(&head, 20);
     push(&head, 4);
     push(&head, 15); 
     push(&head, 85);      
     push(&head, 8);      
     push(&head, 5);      
     push(&head, 55);      
    
     printList(head);    
     reverseK(&head,6);                      
     printf("\n Reversed Linked list \n");
     printList(head);    
     getchar();
}