[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.对每个转置区间进行转置

其实，找前驱和后驱的代码是可以优化的，留在第二遍再优化，而且这样写虽然代码不够简洁，但是可读性稍稍好一些。

 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 ;
    }