package linkedlist.singly;
/*
Reverse a Linked List in groups of given size
Given a linked list, write a function to reverse every k nodes (where k is an input to the function).
Example:
Inputs: 10->20->30->40->50->60->70->80->NULL and k = 30
Output: 30->20->10->60->50->40->80->70->NULL.
Inputs: 10->20->30->40->50->60->70->80->NULL and k = 50
Output: 50->40->30->20->10->80->70->60->NULL.
*/
public class ReverseKNodesInList {
Node startNode=null;
public static void main(String[] args) {
ReverseKNodesInList g = new ReverseKNodesInList();
Node n1 = new Node(10);
Node n2 = new Node(20);
Node n3 = new Node(30);
Node n4 = new Node(40);
Node n5 = new Node(50);
Node n6 = new Node(60);
Node n7 = new Node(70);
Node n8 = new Node(80);
g.startNode = n1;
n1.setNext(n2);
n2.setNext(n3);
n3.setNext(n4);
n4.setNext(n5);
n5.setNext(n6);
n6.setNext(n7);
n7.setNext(n8);
Node rev = kreverseWay1(g.startNode, 3);
g.printLinkList(rev);
//Node rev = kreverseWay2(g.startNode, 7);
//g.printLinkList(rev);
}
private static Node kreverseWay1(Node startNode, int i) {
Node temp = startNode;
Node previousStart = startNode;
Node newStart=null;
Node newLast=null;
boolean firstTime = true;
int count=0;
while(temp!=null){
if(count==i-1){
Node ahead = temp.getNext();
temp.setNext(null);
Node reversed = reverseWay1(previousStart);
if(firstTime){
newStart = reversed;
newLast = previousStart;
firstTime=false;
}else{
newLast.setNext(reversed);
newLast = previousStart;
}
temp=ahead;
count=0;
previousStart=temp;
}else{
temp=temp.getNext();
count++;
}
}
if(previousStart!=null){
Node reversed = reverseWay1(previousStart);
if(newLast!=null){
newLast.setNext(reversed);
}else{
newStart=reversed;
}
}
return newStart;
}
private static Node reverseWay1(Node startNode) {
Node a = null;
Node b=startNode;
while(b!=null){
Node c = b.getNext();
b.setNext(a);
a=b;
b=c;
}
return a;
}
public static Node kreverseWay2(Node list, int k){
Node prev = list;
int i = 0;
//first block special case?
while(list != null && i++ < k){
list = list.getNext();
}
Node retval = reverseWay2(prev, k);
while(list != null){
i = 0;
Node me = list;
while(list != null && i++ < k)
list = list.getNext();
Node end = reverseWay2(me, k);
prev.setNext(end);
prev = me;
}
return retval;
}
public static Node reverseWay2(Node list, int k){
Node prev = null;
while(list != null && k-- > 0){
Node next = list.getNext();
list.setNext(prev);
prev = list;
list = next;
}
return prev;
}
private void printLinkList(Node startNode) {
Node tempNode = startNode;
while(tempNode!=null){
System.out.print(tempNode.getData() + " ");
tempNode = tempNode.getNext();
}
}
}
Questions on Stack, Queues, Linkedlist, Binary Trees, Sorting, Searching, Graphs etc with solution using Java Language.
Sunday, 14 June 2015
Reverse a Linked List in groups of given size
Labels:
Linkedlist
Subscribe to:
Post Comments (Atom)
No comments:
Post a Comment