CareerCup

When you say reverse, does it mean reversing the data ? Or do you mean reverse the order of traversal ?

As per my understanding I'm providing the below example for others to try out

Input:

singly linked list
1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20

and k = 5

Output:

1->2->3->4->5->10->9->8->7->6->15->14->13->12->11->20->19->18->17->16

Note: Take care of corner cases like n%k != 0 (n - number of nodes in LL) when you work out.

Or is the problem like, you have to skip first k nodes, then reverse the next k nodes, then skip the next k nodes, then reverse the next k nodes and so on until the end?

public void reverseList(int k){
		List temp = start;
		int i = 1;
		while(i<k){
			temp = temp.next;
			i++;
		}
	
		List p =temp.next;
		List q = null;
		List r;
		
		while(p != null){
			r = q;
			q = p;
			p = p.next;
			q.next = r;
		}
		
		temp.next = q;
	}

#include <stdio.h>
#include <malloc.h>

typedef struct ll
{
  int i;
  struct ll *next;
}ll;

print_ll(struct ll *pHead)
{
  struct ll *cur_node;
  printf ("head");
  for (cur_node = pHead; cur_node; cur_node = cur_node->next)
    printf ("->%d",cur_node->i);
  printf ("->NULL\n");
}

create_ll(struct ll *pHead, int count)
{
  struct ll *pCur_node;
  struct ll *pPrev_node;
  int i;

  pPrev_node = pHead;
  for (i=1; i <= count; i++)
  {
    pCur_node = malloc (sizeof(struct ll));
    pCur_node->i = i;
    pCur_node->next = NULL;
    pPrev_node->next = pCur_node;
    pPrev_node = pCur_node;
  }
}

struct ll* reverse_ll(struct ll *pStart, int count)
{
  int i;
  struct ll *pCur_node = pStart;
  struct ll *pPrev_node = NULL;
  struct ll *pNext_node = pStart->next;

  for (i= 1; i < count && pNext_node; i++)
  {
    pPrev_node = pCur_node;
    pCur_node = pNext_node;
    pNext_node = pNext_node->next;
    pCur_node->next = pPrev_node;
  }
  pStart->next = pNext_node;
  return pCur_node;
}


process_ll(struct ll *pHead, int count)
{
  int i;
  struct ll *pCur_node = pHead;
  struct ll **pArrayll;

  pArrayll = malloc(sizeof(struct ll*) * count);

  for (i= 1; i < count && pCur_node; i++)
  {
    pCur_node = pCur_node->next;
  }

  while (pCur_node && pCur_node->next)
  {
    pCur_node->next = reverse_ll(pCur_node->next, count);

    for (i= 1; i <= count && pCur_node; i++)
    {
      pCur_node = pCur_node->next;
    }
  }
  
}

int main()
{
  int k;
  struct ll head;
  create_ll(&head, 20);
  printf("Enter the k value:"); 
  scanf("%d",&k); 

  process_ll(head.next, k);
  print_ll(head.next);

}

Output
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:7
head->1->2->3->4->5->6->7->14->13->12->11->10->9->8->20->19->18->17->16->15->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:1
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:2
head->1->2->4->3->6->5->8->7->10->9->12->11->14->13->16->15->18->17->20->19->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:3
head->1->2->3->6->5->4->9->8->7->12->11->10->15->14->13->18->17->16->20->19->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:4
head->1->2->3->4->8->7->6->5->12->11->10->9->16->15->14->13->20->19->18->17->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:5
head->1->2->3->4->5->10->9->8->7->6->15->14->13->12->11->20->19->18->17->16->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:6
head->1->2->3->4->5->6->12->11->10->9->8->7->18->17->16->15->14->13->20->19->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:7
head->1->2->3->4->5->6->7->14->13->12->11->10->9->8->20->19->18->17->16->15->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:8
head->1->2->3->4->5->6->7->8->16->15->14->13->12->11->10->9->20->19->18->17->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:9
head->1->2->3->4->5->6->7->8->9->18->17->16->15->14->13->12->11->10->20->19->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:10
head->1->2->3->4->5->6->7->8->9->10->20->19->18->17->16->15->14->13->12->11->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:11
head->1->2->3->4->5->6->7->8->9->10->11->20->19->18->17->16->15->14->13->12->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:15
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->20->19->18->17->16->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:19
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:20
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->NULL
bash-4.2$ ./ll_reverse 
Enter the k value:18
head->1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->20->19->NULL
bash-4.2$

/* Checks all corner cases, does a best case skip/reversal */

void skip_k_rev_k(struct node *head, int k)
{
struct node *prev, *save, *save_skipped_last, *save_rev_first;

/* Skip k and return if we reach end */
for(int i = 0; i < k; i++) {
if(!head)
return;
prev = head;
head = head->next;
}


if(!head)
return;

/* Save first element in the subset list being reversed */
save_rev_first = head;

/* Reverse entire subset list */
for(int i = 0; i < k; i++) {
/* Break for cases where we run out list since we still need to fixup */
if(!head)
break;
save = head->next;
head->next = prev;
prev = head;
head = save;
}

/* Retrieve last element of the initial skipped list */
save_skipped_last = save_rev_first->next;

/* Point it to the last element of the skipped list */
save_skipped_last->next = prev;

/* Point last element of the now reversed list to the next element of the list it reversed */
save_rev_first->next = head;
}

void skip_k_rev_k(struct node *head, int k)
{
        struct node *prev, *save, *save_skipped_last, *save_rev_first;

        /* Skip k and return if we reach end */
        for(int i = 0; i < k; i++) {
                if(!head)
                        return;
                prev = head;
                head = head->next;
        }


        if(!head)
                return;

        /* Save first element in the subset list being reversed */
        save_rev_first = head;

        /* Reverse entire subset list */
        for(int i = 0; i < k; i++) {
                /* Break for cases where we run out list since we still need to fixup */
                if(!head)
                        break;
                save = head->next;
                head->next = prev;
                prev = head;
                head = save;
        }

        /* Retrieve last element of the initial skipped list */
        save_skipped_last = save_rev_first->next;

        /* Point it to the last element of the skipped list */
        save_skipped_last->next = prev;

        /* Point last element of the now reversed list to the next element of the list it reversed */
        save_rev_first->next = head;
}

public static void reversePartial(LinkedList<Integer> list, int n){
		List<Integer> l = new ArrayList<Integer>();
		for(int i = 0; i < n; i++){
			int num = list.poll();
			l.add(num);
		}

		Collections.reverse(list);
		for(int i = l.size() - 1; i >= 0; i--){
			list.add(0, l.get(i));
		}
	}

Solution in Java ....

public Node reverseNodes(Node head){
		
		Node current = head;
		Node end = head;
		Node start = null;
		
		Node next;
		
		while(current != null){
			for (int i = 0; i < 2; i++){
				if(end == null)
					break;
				end = end.next;
			}
		
			start = end;
			
			if(end != null){
				end = end.next;
				Node prev = null;
				
				for (int i = 0; i< 3; i++){
					if(end == null)
						break;
					next = end.next;
					end.next = prev;
					prev = end;
					end = next;
				}
			
			if(prev != null)
				start.next = prev;
			
			for(int i = 0; i < 3; i++){
				start = start.next;
			}
			if(start != null)
				start.next = end;
			}
			current = end;
		}
		
			
		return head;
	}

Simple solution with Stack, taking into account all the conditions:

public boolean skipAndReverse(MyNode<T> current, int k)
	{
		if(k<2 || current == null){
			return false;
		}
		
		for(int y = 0; y<k;y++)
		{
			current = current.next;
			if(current == null){
				return false;
			}
		}
		
		Stack<T> s = new Stack<>();		
		MyNode<T> temp = current;
		
		while( current !=null)
		{	
			for(int x = 0; x < k; x++)
			{
				s.push(temp.data);
				temp = temp.next;
				
				if(temp== null){
					break;
				}
			}
				
			temp = current;
			
			while(!s.isEmpty())
			{
				T val = s.pop();
				temp.data = val;
				temp = temp.next;
			}
		
			current = temp;
		}
		
		return true;

}

public Node ReverseFromKthNode(Node head, int k)
        {
            if(head==null || head.Next==null)
            {
                return head;
            }
            Node curr = head;
            int i = 0;
            while(i<k)
            {
                curr = curr.Next;
                i++;
                if (curr==null)
                {
                    return null;
                }
            }
            Node next;
            Node prev = null;
            while (curr!=null)
            {
                next = curr.Next;
                curr.Next = prev;
                prev = curr;
                curr = next;
            }
            return prev;
        }

node *reverse(node *head){
int i=1;
node *prev, *h, *n, *t, *q;
prev =NULL;
h = head;
while(i<5){

        h=h->next;
    i++;
    }
        t =h->next;
        q=t;
    while(t!=NULL)
    {
        i=0;
        q= t;
        while(i<5){
    n = t->next;
    t->next = prev;
    prev = t;
    t = n;
    i++;
        }
        h->next = prev;
        h=q;
        prev = NULL;
}

return head;
}

//RECURSIVELY REVERSE LINKED LISTS
node* reverseRecursively(node** list) {
if (!*list) return;

//SET THE LIST WITH FIRST AND REST INSTANCES
node* first = *list;
node* rest = first->next;

if (!rest) return;

reverseRecursively(&rest);

//F->N->N = F makes the next node point to itself to reverse its direction
//AND THEN F->N is made to point NULL
first->next->next = first;
first->next = NULL;

//FIX THE HEAD POINTER
*list = rest;
return *list;
}

//SKIP K ELEMENTS IN THE LIST AND THEN
//RECURSIVELY REVERSE THE REMAINING LINKED LISTS
node* reverseKNodes(node** list, int k) {
if (!*list) return;

node* head = *list;

while (k >= 0) {
*list = (*list)->next;
k--;
}

(*list)->next = reverseRecursively(&(*list)->next);
return head;
}

public static void deletelast(Node x)
	{
		Node one=x;
		Node two=x;
		int count=0;
		if(one.next==null)
		{
			one=null;
		}
		else
		{
		while(one.next!=null)
		{
			one=one.next;
			if(count==1)
				two=two.next;
			else if(count<1)
				count++;
		}
		
		two.next=null;
		}
	}


public static Node reverselink(Node one)
	{
		if(one.next==null)
		{
			if(newfirst!=null)
			{
		y.next=one;
		one.next=null;
		y=one;
		
			}
			else
			{
				y=newfirst=one;
		
			}
			deletelast(one);
			return newfirst;
		}
		Node temp=one;
		while(temp.next!=null)
		{
			temp=temp.next;
		}
		if(newfirst==null)
		{
		temp.next=null;
		y=newfirst=temp;
		}
		else
		{
			y.next=temp;
			temp.next=null;
			y=temp;
			
		}
		deletelast(one);
		reverselink(one);
		return newfirst;
	}

public static Node partialrev(int i,Node x)
	{
		Node one=x;
		int z=1;
		Node onelag=x;
		int count=0;
		while(z<i)
		{
			one=one.next;
			if(count>0)
				onelag=onelag.next;
			z++;
			count++;
		}
		Node two=one.next;
		onelag.next.next=null;
		Node rev=reverselink(two);
		one.next=rev;
		return x;
		
	}

import java.util.Stack;

public class SkipReverseKNodes {
	
	public void reverse(Node head,int k){
		if(k<=1 || k>=head.getSize()){
			System.out.println("Enter a value greater than 1 and less than "+head.getSize());
			return;
		}
		Node runner=head;
		Node current=head;
		for(int i=0;i<k-1;i++){
			runner=runner.next;
			current=current.next;
		}
		runner=current.next;
		while(runner!=null){
			Stack<Integer> s=new Stack<Integer>();
			for(int i=0;i<k;i++){
				s.push(runner.data);
				runner=runner.next;
				if(runner==null) break;
			}
			while(!s.isEmpty()){
				current.next.data=s.pop();
				current=current.next;
			}
		}
	}
	
	public static void main(String[] args) {
		Node head=new Node(1);
		head.appendNode(2);
		head.appendNode(3);
		head.appendNode(4);
		head.appendNode(5);
		head.appendNode(6);
		head.appendNode(7);
		head.appendNode(8);
		
		SkipReverseKNodes s=new SkipReverseKNodes();
		
		Node n=head;
		while(n!=null){
			System.out.print(n.data+" ");
			n=n.next;
		}

		System.out.println();
		s.reverse(head, 2);
		n=head;
		while(n!=null){
			System.out.print(n.data+" ");
			n=n.next;
		}
	}
}

This is _easy_ so must be _homework_.