1. Traverse k nodes forward and set temp to the k+1th node 2. Reverse k nodes traversed in step 1. Here is a post on how to reverse a linked list: Reverse a Linked List 3. Set next of the last node in this k length list to temp. 4. Traverse next k nodes which are to be skipped. 5. Recursively call steps 1-3 for reversing next k nodes.
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.
Thanks, -Team IDeserve
Algorithm Visualization
Code Snippet
package com.ideserve.questions.saurabh;
/**
* <b>IDeserve <br>
* <a href="https://www.youtube.com/c/IDeserve">https://www.youtube.com/c/IDeserve</a>
* Reverse every alternate k nodes of a Linked List.
*
* @author Saurabh
*/
public class LinkedList {
private ListNode head;
public void add(int data) {
if (head == null) {
head = new ListNode(data);
return;
}
ListNode n = new ListNode(data);
ListNode tmp = head;
while (tmp.next != null) {
tmp = tmp.next;
}
tmp.next = n;
}
public void printList() {
if (head == null) {
System.out.println("List is empty!");
return;
}
ListNode tmp = head;
while (tmp != null) {
System.out.print(tmp.data + " -> ");
tmp = tmp.next;
}
System.out.println("null");
}
public void reverseKAlternateNodes(int k) {
if (head == null || head.next == null || k < 2) {
return;
}
head = reverseKAlternateNodes(head, k);
}
// Reverse alternate k nodes
public ListNode reverseKAlternateNodes(ListNode head, int k) {
if (head == null || head.next == null || k < 2) {
return head;
}
// get k+1th node
ListNode temp = head;
int i = 0;
while (i < k && temp != null) {
temp = temp.next;
i++;
}
// reverse nodes upto k nodes traversed previously
head = reverseKNodes(head, k);
ListNode next = head;
while (next.next != null) {
next = next.next;
}
next.next = temp;
// Traverse next k nodes
i = 0;
ListNode prev = null;
while (i < k && temp != null) {
prev = temp;
temp = temp.next;
i++;
}
if (temp != null) {
prev.next = this.reverseKAlternateNodes(temp, k);
}
return head;
}
// Reverse k nodes starting from start node
private ListNode reverseKNodes(ListNode start, int k) {
if (start == null || k < 2) {
return null;
}
ListNode prev = null;
ListNode curr = start;
ListNode next = null;
int i = 1;
while (curr.next != null && i < k) {
next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
i++;
}
next = curr.next;
curr.next = prev;
return curr;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
for (int i = 1; i <= 10; i++) {
list.add(i);
}
list.printList();
list.reverseKAlternateNodes(4);
list.printList();
}
}
class ListNode {
int data;
ListNode next;
public ListNode(int data) {
this.data = data;
}
}
Order of the Algorithm
Time Complexity is O(n) Space Complexity is O(1)
Contribution
Sincere thanks from IDeserve community to Saurabh Kumar for compiling current post.
Saurabh Kumar
Like IDeserve?
Support us by whitelisting IDeserve in your ad-blocker.