Reverse Linked List – single pointer – in group of K

Posted on by

Reverse a link list using one/single pointer.

We first try to device straightforward solution to reverse a linked list recursively. For example, given a linked list 1->2->3->4->5->null, how we can reverse this? Let’s start with straightforward solution using two temp pointers. We will basically keep a new pointer to append nodes from the list into the front of new pointer. Below is both recursive and iterative solution in O(n) time. 

public static ListNode reverse(ListNode head){
	if(head == null || head.next == null){
		return head;
	}
	
	ListNode reversed = null;
	ListNode temp = null;
	while(head != null){
		temp = head.next;
		head.next = reversed;
		reversed = head;
		head = temp;
	}
	
	return reversed;
}

//recursive: Idea is to take each element from the list and add in front of another list called reversed
public static ListNode reverse(ListNode head, ListNode reversed){
	if(head==null) return reversed;
	ListNode current = head;
	head = head.next;
	current.next = reversed;
	return reverse(head, current);
}

 
Using Single Pointer
Now, how to do it with a single pointer? Unfortunately it is not possible in Java but We can do some memory trick in C/C++ to do the same as below.

//now we can eliminate the use of next temporary pointer by using pointer swap (it is possible only in c as Java is a pass by value but pointer swap needs pass by reference

#define pointer_swap(a,b) ((int)(a)) ^= ((int)(b)) ^= ((int)(a)) ^= ((int)(b))

struct list * reverse_ll(struct list * head){
  struct list * temp = NULL;
  while(head) {
      pointer_swap(temp,head->next);
      pointer_swap(temp,head); 
  }
  return temp;

 
Reverse Linked List In Group of Size K
For example, given list 1->2->3->4->5->6->7->null and k = 3 then the output should be 3->2->1->6->5->4->7->null. How we do that? As previously we were appending the list nodes in front of another to reverse it so, to reverse in groups of k we just need to stop the appending process at kth step and reset the reverse process again at (k+1) th node. Below is the O(n) time implementation of this idea. 

public static ListNode reverse(ListNode head, int k){
	if(head == null || head.next == null){
		return head;
	}
	
	ListNode prevHead = head;
	ListNode reversed = null;
	ListNode temp = null;
	int count = 0;
	while(head != null && count < k){
		temp = head.next;
		head.next = reversed;
		reversed = head;
		head = temp;
		count++;
	}
	
	if(prevHead != null){
		prevHead.next = reverse(head, k);
	}
	
	return reversed;
}