[leetcode]Reverse Nodes in k-Group

新しいブログアドレス:
 
[leetcode]Reverse Nodes in k-Group
 
Reverse Nodes in k-Group
Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.
If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.
You may not alter the values in the nodes, only nodes itself may be changed.
Only constant memory is allowed.
For example,
Given this linked list: 1->2->3->4->5
For k = 2, you should return: 2->1->4->3->5
For k = 3, you should return: 3->2->1->4->5
この問題に似ていますが、反復の要求が加わっただけで、直接的な考えです.
1.転置区間を算出する個数
2.各転置区間について、その前駆体と後駆動体を見つける
3.各転置区間を転置する
実際には、前駆者と後駆者を探すコードは最適化でき、2回目に残して最適化することができ、このように書くのはコードが簡潔ではありませんが、可読性は少し良いです.

 public ListNode reverseKGroup(ListNode head, int k) {
    	int length = getLength(head);
    	if(length < k || k <= 1){
    		return head;
    	}
    	ListNode hhead = new ListNode(0);
    	hhead.next = head;
    	for(int i = 0; i < length / k; i++){
    		ListNode pre = getStartInLoopN(hhead, i, k);
    		ListNode post = getEndInLoopN(pre, k);
    		ListNode iPre = pre;
    		ListNode iNode = pre.next;
    		ListNode iPost = iNode.next;
    		while(iNode != post){
    			if(iNode == pre.next){
    				iNode.next = post;
    				iPre = iNode;
    				iNode = iPost;
    				iPost = iNode.next;
    			}else if(iNode.next == post){
    				pre.next = iNode;
    				iNode.next = iPre;
    				iNode = post;
    			}else{
    				iNode.next = iPre;
    				iPre = iNode;
    				iNode = iPost;
    				iPost = iNode.next;
    			}
    		}
    	}
    	return hhead.next;
    }
    private ListNode getStartInLoopN(ListNode hhead,int n,int k){
    	for(int i = 0 ; i < n*k; i++){
    		hhead = hhead.next;
    	}
    	return hhead;    	
    }
    private ListNode getEndInLoopN(ListNode startNode,int k){
    	for(int i = 0 ; i < k + 1; i++){
    		startNode = startNode.next;
    	}
    	return startNode;
    }
    
    private int getLength(ListNode head){
    	int count = 0;
    	while(head != null){
    		head = head.next;
    		count++;
    	}
    	return count ;
    }