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