Thursday, May 2, 2013

Reverse k nodes in a linkedlist


public class ReverseKNodes {
public static void main(String[] args) {
lnode a = new lnode();
a.setData(1);
lnode b = new lnode();
b.setData(2);
lnode c = new lnode();
c.setData(3);
lnode d = new lnode();
d.setData(4);
lnode e = new lnode();
e.setData(5);
lnode f = new lnode();
f.setData(6);
lnode g = new lnode();
g.setData(7);
lnode h = new lnode();
h.setData(8);
lnode i = new lnode();
i.setData(9);
lnode j = new lnode();
j.setData(10);
lnode k = new lnode();
k.setData(11);
a.setNext(b);
b.setNext(c);
c.setNext(d);
d.setNext(e);
e.setNext(f);
f.setNext(g);
g.setNext(h);
h.setNext(i);
i.setNext(j);
j.setNext(k);
ReverseKNodes r = new ReverseKNodes();
lnode finalhead = r.ReverseKnodes(3, a);
while(finalhead != null)
{
System.out.println(finalhead.getData());
finalhead = finalhead.getNext();
}
}
public lnode ReverseKnodes(int K, lnode head)
{
int count=0;
lnode cur= head , newHead,temp=null,next=null,poc=null,fpoc= null;
if(HasKNodes(cur, K-1))
{
newHead = GetPlusOneNode(K-1, cur);
}
else
newHead = head;
while(cur!=null && HasKNodes(cur, K))
{
fpoc = poc;
temp = GetPlusOneNode(K, cur);
poc = cur;
int i=0;
while(i{
next = cur.getNext();
cur.setNext(temp);
temp = cur;
cur = next;
i++;
}
if(count != 0)
fpoc.setNext(temp);
count++;
}
return newHead;
}
public boolean HasKNodes(lnode head, int K) {
lnode node;
int i;
for(i=0;head != null && i <= K -1;i++,head = head.getNext());
if(i==K)
{
return true;
}
else
return false;
}
public lnode GetPlusOneNode(int K,lnode head)
{
int i;
lnode kth;
for(i=0,kth=head;kth!= null&& i<= K-1;i++,kth = kth.getNext());
if(i==K && kth != null)
{
return kth;
}
return head.getNext();
}
}
class lnode {
private int data;
private lnode next;
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public lnode getNext() {
return next;
}
public void setNext(lnode next) {
this.next = next;
}
}

No comments: