LeetCode 206 Reverse Linked List

LeetCode

<div>

Given the head of a singly linked list, reverse the list, and return the reversed list.

Example 1:

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

Example 2:

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

Example 3:

<pre>Input: head = [] Output: [] </pre>

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

</div>

题目大意：

反转LL

解题思路：

简单题，但是经典题。循环体为，左方一个单独节点，右方为一个LL，将LL的首节点指向单独节点

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. 利用模板，由于首节点会变，所以引入fake_node
2. 空节点的处理

Python代码：

def reverseList(self, head: ListNode) -> ListNode:
	if not head:
		return None
	fake_head = ListNode(0)
	fake_head.next = head
	start, end = fake_head, head
	while end.next:
		# 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
	return fake_head.next

算法分析：

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