Algorithms
Reverse Linked List – single pointer – in group of K
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;
}