LeetCode 092 Reverse Linked List II

LeetCode

<div>

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

Example 1:

<pre>Input: head = [1,2,3,4,5], left = 2, right = 4 Output: [1,4,3,2,5] </pre>

Example 2:

<pre>Input: head = [5], left = 1, right = 1 Output: [5] </pre>

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

Follow up: Could you do it in one pass?</div>

题目大意：

反转链表中的子链表[left, right]，start和end是1-index位置, inclusive

解题思路：

锁定start和end节点，将end的后续节点一个个加到start直接后续

LeetCode 206 Reverse Linked List 反转整个LL LeetCode 092 Reverse Linked List II 反转部分LL，此题更加一般化

模板： 不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> ... -> end(group n+1) -> NodeA （前状态） -> ...

1. 找出start和end，start为反转部分的前一个，end为反转部分的首个节点
2. 循环删除end直接后，再加入到start直接后

Python代码：

start, end = fake_head, head
while <反转链表长度>:
	# 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

解题步骤：

N/A

注意事项：

1. 经典题，见LeetCode 2074 Reverse Nodes in Even Length Groups。 思路是锁定start和end节点，将end的后续节点一个个加到start直接后续
2. 第二个循环中，right要记得减一，否则死循环

Python代码：

def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode:
	left, right = left - 1, right - 1
	fake_head = ListNode(0)
	fake_head.next = head
	it = fake_head
	while left > 0:
		it = it.next
		left -= 1
		right -= 1
	start, end = it, it.next
	while right > 0:
		moved_node, end.next = end.next, end.next.next # delete a node
		start.next, moved_node.next = moved_node, start.next # insert a node
		right -= 1 # remember
	return fake_head.next

算法分析：

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