每日一题（2020-05-16）25. K 个一组翻转链表

[25. K 个一组翻转链表]

难度 困难

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

示例：

给你这个链表：

1->2->3->4->5

当 k = 2 时，应当返回:

2->1->4->3->5

当 k = 3 时，应当返回:

3->2->1->4->5

说明：

• 你的算法只能使用常数的额外空间。
• 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group

解法一：

class Solution {
	    public ListNode reverseKGroup(ListNode head, int k) {
	    	ListNode ans = new ListNode(-1);
	    	ans.next = head;
	    	
	    	ListNode start = head;	//一组待翻转节点的起点
	    	ListNode end = head;	//一组待翻转节点的终点
	    	
	    	ListNode pre = ans;	//指向已翻转序列的终点，用来连接已翻转序列和未翻转序列
	    	
	    	while(start != null) {
	    		end = start;
	    		//使 end 指向新一组待翻转节点的终点
	    		for(int j = 1; j < k && end != null; j++) {
	    			end = end.next;
	    		}
	    		//该组节点不足 k 个，剩余的节点保持原有顺序
	    		if(end == null) {
	    			return ans.next;
	    		}
	    		pre.next = end;	//连接已翻转序列和未翻转序列
	    		pre = start;	//更新已翻转序列的尾部（因为该组的起始节点经过翻转后变为末端节点， 因此 start 的位置变为翻转后序列的终点）
	    		
	            ListNode startNext = end.next;	//下一组待翻转的起点
	           
	    		//翻转该组节点（依次将start 所指的节点添加到end节点的后面）
	            //例如：end节点指向 3， start依次指向1 ，2 
	            //'1'——>2——>3	'2'——>3——>1	3——>2——>1
	    		for(int j = 1; j < k; j++) {
	    			ListNode temp = start.next;	//下一个要翻转的节点
	    			start.next = end.next;
	    			end.next = start;
	    			start = temp;
	    		}
                
	    		start = startNext;	
	    	}
	    	return ans.next;
	    }
	    
  }
           

解法二：递归

class Solution {
	     public ListNode reverseKGroup(ListNode head, int k) {
	        if (head == null || k == 1) {
	            return head;
	        }

	        ListNode start = head,	end = head;
	        ListNode remain = null;	//指向剩余未翻转序列的起点

	        for (int i = 1; i < k && end != null; i++) {
	            end = end.next;
	        }
	        
	        //该组节点不足 k 个，剩余的节点保持原有顺序
	        if(end == null)	return head;
	        
	        remain = end.next;
	        end.next = null;
	        head = reverseList(head);	//翻转一组节点
	        start.next = reverseKGroup(remain, k);	//连接剩余该组节点后的节点

	        return head;
	    }

	    private ListNode reverseList(ListNode head) {
	        if (head == null || head.next == null) {
	            return head;
	        }

	        ListNode prev = null;	//已翻转序列的头结点
	        ListNode current = head;	//当前需要翻转的节点
	        //采用头插法进行翻转
	        while (current != null) {
	            ListNode next = current.next;
	            current.next = prev;
	            prev = current;
	            current = next;
	        }

	        return prev;
	    }

	}