2. Reverse a linked list for a given size

2. Reverse a linked list for a given size

Problem link :- click here

package Linked_List;

public class LinkedList__2
{

	static void reverseAPart(LinkedList list, int k)
	{
		//finding the last element up-to which we have to reverse
		Node temp = list.head;
		
		for(int i=0; i<k-1; i++)
			temp = temp.next;
		
		Node last_node = temp;
		//taking first_node as the first node which is not involved in reversing
		//this node is required to link after reversing.
		Node first_node = last_node.next;
		
		
		//we are doing this because we are using the condition like that
		last_node.next = null;
		
		Node prev, cur, next;
		prev = null;
		cur = list.head;
		
		while(cur != null)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
		}
		//after reversing our last element should point to the first_node
		//but have we stored that.
		//But after reversing our last element will be the head of the list right?!!
		list.head.next = first_node;
		
		//Now the major step we have to update the head of the list.
		list.head = prev;
		//we should do this after pointing the last node to the first_node
		//because we are using head for that. If we do this step first then last node
		//of the reversed list will not point to the first_node.
	}
	
	//this is the actual solution 
	static Node reverseInGroup(Node head, int k)
	{
		Node prev, cur, next;
		prev = null;
		cur = head;
		next = cur.next;
		
		int count = 0;
		while(cur != null  &&  count < k)
		{
			next = cur.next;
			
			cur.next = prev;
			
			prev = cur;
			cur = next;
			count++;
		}
		//till here we just reversed a group 
		//now the head will be 'prev' and the last node of this group is earlier head
		//now we have to reverse the next group and connect that group's head with
		//the next of this group's last node
		if(next != null)
			head.next = reverseInGroup(next, k);
		
		//now return head of this group
		return prev;
	}
	
	public static void main(String[] args)
	{
		LinkedList list = new LinkedList();
		list.push(1);
		list.push(2);
		list.push(2);
		list.push(4);
		list.push(5);
		list.push(6);
		list.push(7);
		list.push(8);
		
		System.out.println("Linked List : ");
		printList(list);

		int k = 3;
		list.head = reverseInGroup(list.head, k);
		System.out.println("\nLinked List after reversing : ");
		printList(list);
	}

	static void printList(LinkedList list)
	{
		for(Node temp=list.head; temp!=null; temp=temp.next)
			System.out.print(temp.data + "-> ");
		System.out.println("null");
	}
}

Time complexity :- O(n)
Space complexity :- O(1)