Last active
August 29, 2015 14:02
-
-
Save flexelem/83d149dafc01673a0215 to your computer and use it in GitHub Desktop.
reverse a LinkedList by k size slots with using a stack
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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 file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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