LeetCode 092 Reverse Linked List II

LeetCode

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:

Input: head = [1,2,3,4,5], left = 2, right = 4
Output: [1,4,3,2,5]

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

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?

题目大意：

反转链表中的子链表[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)