Skip to content

Instantly share code, notes, and snippets.

@flexelem
Last active August 29, 2015 14:02
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save flexelem/83d149dafc01673a0215 to your computer and use it in GitHub Desktop.
Save flexelem/83d149dafc01673a0215 to your computer and use it in GitHub Desktop.
reverse a LinkedList by k size slots with using a stack
public class LinkedList {
public class Node {
int data;
Node next;
public Node(int item) {
this.data = item;
}
}
public Node head;
public void insert(int item) {
if (head == null) {
head = new Node(item);
return;
}
Node currentNode = head;
while (currentNode.next != null) {
currentNode = currentNode.next;
}
currentNode.next = new Node(item);
}
public void print() {
Node curr = head;
while (curr != null) {
System.out.println(curr.data);
curr = curr.next;
}
}
}
// this method will reverse the references by using a stack
public void reverseLinkedListKSizeSlots(LinkedList list, int k) {
Node currentNode = list.head;
Node headNext = null;
Node headPrev = null;
Node prev = list.head;
int x = 1;
Stack<Node> stack = new Stack<>();
while (currentNode != null) {
currentNode = prev.next;
if (x <= k) {
stack.push(prev);
} else {
if (headNext == null && headPrev == null) {
headPrev = stack.pop();
Node temp = headPrev;
while (!stack.isEmpty()) {
Node t = stack.pop();
temp.next = t;
temp = temp.next;
}
list.head = headPrev;
headPrev = temp;
x = 1;
stack.push(prev);
} else {
headNext = stack.pop();
Node temp = headNext;
while (!stack.isEmpty()) {
Node t = stack.pop();
temp.next = t;
temp = temp.next;
}
headPrev.next = headNext;
headPrev = temp;
x = 1;
stack.push(prev);
}
}
x++;
prev = prev.next;
}
if (!stack.isEmpty()) {
if (headNext == null && headPrev == null) {
headPrev = stack.pop();
Node temp = headPrev;
while (!stack.isEmpty()) {
Node t = stack.pop();
temp.next = t;
temp = temp.next;
}
list.head = headPrev;
headPrev = temp;
temp.next = null;
} else {
headNext = stack.pop();
Node temp = headNext;
while (!stack.isEmpty()) {
Node t = stack.pop();
temp.next = t;
temp = temp.next;
}
headPrev.next = headNext;
headPrev = temp;
temp.next = null;
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment