LeetCode 206 Reverse Linked List

LeetCode

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

Example 1:

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

Example 2:

Input: head = [1,2]
Output: [2,1]

Example 3:

Input: head = []
Output: []

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?

题目大意：

反转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)