LeetCode 2074 Reverse Nodes in Even Length Groups

LeetCode 2074 Reverse Nodes in Even Length Groups

<div>

You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

• The 1<sup>st</sup> node is assigned to the first group.
• The 2<sup>nd</sup> and the 3<sup>rd</sup> nodes are assigned to the second group.
• The 4<sup>th</sup>, 5<sup>th</sup>, and 6<sup>th</sup> nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:

<pre>Input: head = [5,2,6,3,9,1,7,3,8,4] Output: [5,6,2,3,9,1,4,8,3,7] Explanation:

• The length of the first group is 1, which is odd, hence no reversal occurrs.
• The length of the second group is 2, which is even, hence the nodes are reversed.
• The length of the third group is 3, which is odd, hence no reversal occurrs.
• The length of the last group is 4, which is even, hence the nodes are reversed. </pre>

Example 2:

<pre>Input: head = [1,1,0,6] Output: [1,0,1,6] Explanation:

• The length of the first group is 1. No reversal occurrs.
• The length of the second group is 2. The nodes are reversed.
• The length of the last group is 1. No reversal occurrs. </pre>

Example 3:

<pre>Input: head = [2,1] Output: [2,1] Explanation:

• The length of the first group is 1. No reversal occurrs.
• The length of the last group is 1. No reversal occurrs. </pre>

Example 4:

<pre>Input: head = [8] Output: [8] Explanation: There is only one group whose length is 1. No reversal occurrs. </pre>

Constraints:

• The number of nodes in the list is in the range [1, 10<sup>5</sup>].
• 0 <= Node.val <= 10<sup>5</sup>

</div>

题目大意：

把链表分成1,2,3..n大小的组。若该组大小为偶数，反转链表。

解题思路：

一开始考虑分奇偶组来处理，但忽略了最后一组也可能为偶数。用stack来，先做统计，若为偶数，就出栈且反转。
后来为了程序更加简洁，就独立一个函数出来按组处理。而每组用迭代将后续节点一个个加到上一组末节点和首节点之间。

解题步骤：

1. 按组处理
2. 每组先统计个数，如果为偶数，反转链表

start(group n) -> end(group n+1, head of group n+1 will become new tail after reversed) -> ...
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> ... -> end(group n+1) -> NodeA （前状态） -> ...

注意事项：

1. 若最后一组不满为偶数，也要逆转。
2. 反转链表时，个数为这组大小减一，因为该组的首节点不用反转。

Python代码：

def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
	group, cur = 2, head
	while cur.next:
		cur = self.process_one_group(cur, group)
		group += 1
	return head

def process_one_group(self, tail_of_last: ListNode, n: int) -> ListNode:
	cur, count = tail_of_last, 0
	while cur.next and count < n:
		cur = cur.next
		count += 1
	if count % 2 == 0:
		start, end = tail_of_last, tail_of_last.next
		for i in range(count - 1):
			# delete the node
			moved_node, end.next = end.next, end.next.next
			# insert the moved_node
			start.next, moved_node.next = moved_node, start.next
	cur = tail_of_last
	for i in range(count):
		cur = cur.next
	return cur

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。