Algorithm 02 : 以K个元素为一组逆转链表

Question : Reverse a Linked List in groups of given size K.

问题：以K个元素为一组逆转链表。

/**
  * @author YuHuang
  * @vision 2011-10-03
  * This program is only for algorithm training.
  *
  */


class Node {
        public int data;
        public Node next;
}

class LinkedList {
        private Node head;
        private int size;

        public LinkedList(int size){
                this(new int[size]);
        }

        public LinkedList(int[] initArray){
                int len = initArray.length;
                if(len>0){
                        int count=len;
                        Node preNode=null;

                        while(--count>=0){
                                Node node = new Node();
                                node.data=initArray[count];
                                node.next=preNode;
                                preNode=node;
                        }
                        head = new Node();
                        head.next=preNode;
                }
                this.size = len;
        }

        public Node getHead() {
                return this.head;
        }

        public void resetHead(Node node){
                this.head.next=node;
        }
}

public class ReverseLinkedListByGroup {

        public static void doReverse(LinkedList list,int k){
                Node prev=null,next=null;
                Node r=null;
                Node head=null;

                int count;

                if(list==null){
                        return;
                }

                Node current = list.getHead().next;
                Node p;

                while(current!=null){
                        count=k;
                        p=current;
                        while(current!=null && --count>=0){
                                next = current.next;
                                current.next=prev;
                                prev = current;
                                current = next;
                        }

                        if(r==null) {
                                r=prev;
                        }else{
                                head.next=prev;
                        }
                        head=p;
                        head.next=null; //remember to set null to head.next in order to stop the progrom
                }
                list.resetHead(r);
        }


        public static void main(String[] args){
                int[] initArray=new int[]{1,2,3,4,5,6,7,8,9,10};
                LinkedList list=new LinkedList(initArray);

                Node node = list.getHead().next;

                System.out.println("Before Reversed : ");
                while(node!=null){
                        System.out.print(node.data+" ");
                        node = node.next;
                }
                System.out.println();

                ReverseLinkedListByGroup.doReverse(list,3);
                node=list.getHead().next;

                System.out.println("After Reversed : ");
                while(node!=null){
                        System.out.print(node.data+" ");
                        node = node.next;
                }
                System.out.println();

        }
}

运行结果为：

Lab-Computer-0db2f6:JavaExercises labuser$ java ReverseLinkedListByGroup
Before Reversed :
1 2 3 4 5 6 7 8 9 10
After Reversed :
3 2 1 6 5 4 9 8 7 10