LeetCode第25题思悟——K 个一组翻转链表（reverse-nodes-in-k-group）

知识点预告

1. 重复性操作的处理方法：使用双重循环和递归的方法处理；
2. 边界变量的选择：简单变量较好；

题目要求

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-nodes-in-k-group
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例

给定这个链表：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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的思路

链表翻转是基本操作，该题是K个链表翻转一次，所以我的思路是首先找到翻转操作的边界，然后执行反转操作，直到找不到边界；

public ListNode reverseKGroup(ListNode head, int k) {
	ListNode emptyHead=new ListNode(-1);
	emptyHead.next=head;
	ListNode newHead=emptyHead;
	ListNode newTail;
	ListNode parentNode;
	ListNode currentNode;
	ListNode nextNode=newHead.next;
	int reverseNum;
	ListNode reverseBorder=newHead.next;
	while(true){
		reverseNum=k;
		while(reverseNum>0&&reverseBorder!=null){
			reverseBorder=reverseBorder.next;
			reverseNum--;
		}
		if(reverseBorder==null){
			if(reverseNum!=0){
				break;
			}
		}
		//开始反转链表
		newTail=nextNode;
		while(nextNode!=reverseBorder){
			currentNode=nextNode;
			nextNode=currentNode.next;
			currentNode.next=newHead;
			newHead=currentNode;
		}
		parentNode=newTail.next;
		newTail.next=nextNode;
		parentNode.next=newHead;
		newHead=newTail;
	}
	return emptyHead.next;
}

优秀解法

//解法A
public static void main(String[] args){
	ListNode first= ListNode.createNode(new int[]{1,2,3,4,5});
	ListNode result=reverseKGroup(first,5);
	while(result!=null){
		System.out.print(result.val+" ");
		result=result.next;
	}
}
public ListNode reverseKGroup(ListNode head, int k) {
	if (head == null){
		return head;
	}
	int temp_k = k;
	ListNode tempNode = head;
	while(temp_k>0){
		if(tempNode == null){
			return head;
		}
		tempNode = tempNode.next;
		temp_k--;
	}
	ListNode preNode = null;
	ListNode curNode = head;
	ListNode nextNode = null;
	temp_k = k;
	while (temp_k>0){
		nextNode = curNode.next;
		curNode.next = preNode;
		preNode = curNode;
		curNode = nextNode;
		temp_k--;
	}
	head.next = reverseKGroup(nextNode,k);
	return preNode;
}

//解法B
public ListNode reverseKGroup(ListNode head, int k) {
	ListNode dummy = new ListNode(0), prev = dummy, curr = head, next;
	dummy.next = head;
	int length = 0;
	while(head != null) {
		length++;
		head = head.next;
	}
	head = dummy.next;
	for(int i = 0; i < length / k; i++) {
		for(int j = 0; j < k - 1; j++) {
			next = curr.next;
			curr.next = next.next;
			next.next = prev.next;
			prev.next = next;
		}
		prev = curr;
		curr = prev.next;
	}
	return dummy.next;
}

差异分析

解法A使用递归的处理手段完成“每K次翻转一次”的语义；解法A实际上使用tempNode去判断是否可以进行下一次翻转，在翻转过程中使用int型变量做条件判断；

解法B首先遍历链表，求得长度后通过双重循环完成翻转操作；

知识点小结

1. 重复性操作可使用双重循环和递归的方法处理；
2. 边界变量的选择应选择简单变量较好；