刷题记录：反转链表

反转链表并不是很难，但由于我太久没刷题全忘了。
我第一次写的代码：

def ReverseList(self , head: ListNode) -> ListNode:
	if head == None:			# 检查输入是否为空
		return head
        
	p, q = head, head.next		# 判断是否只有一个结点
	if q == None:				# 如果只有一个结点，则返回该结点
		return head
        
	s = head.next.next			# 判断是否只有两个结点
	if s == None:				# 如果只有两个结点，则反转两个结点并返回
		p.next = None
		q.next = p
		return q
        
	p.next = None				# 如果结点大于等于3，通过循环反转链表
	while q != None:			# 具体思想：用s保存q后的结点，将p赋给q.next
		q.next = p				# 此时，q与原来的链表断开了，但是有s记录断开的位置
		p = q					# 让p = q，使p始终作为反转后的链表的表头
		q = s					# q = s，使q回到旧链表的表头
								# 当s.next = None时，s此时位于表尾
		if s != None:			# 当s = None时，q在表尾，但尚未结束循环，所以需要判断s
			s = s.next			# 最终，q = None时结束循环，新链表表头为p
                
	return p

我写完后感叹：简单是挺简单的，就是我给整复杂了。
然后我准备玩点花的。
于是就有了下面的代码：

def ReverseList(self , head: ListNode) -> ListNode:
	p = head
	if p == None:				# 老样子，先判断链表是否为空
		return p
        
	head = None
	while p != None:
		q = ListNode(p.val)		# 然后！新建结点并用头插法新建列表
		q.next = head			# 我可太聪明辣
		head = q
		p = p.next
        
	return head

虽然是对的，但我还是觉得还能再优化优化。
毕竟，这种解决方法我是真的拿不出手。
随后我去翻看题解和讨论，我大惊失色，原来我不只把反转链表整复杂了一点。
在看完双链表求解之后我修改了自己的代码。

def ReverseList(self , head: ListNode) -> ListNode:
	p = head				# p作为原链表的头
	head = None				# head作为新链表的头
	while p != None:		# 在原链表还存在结点时
		q = p.next			# 使用q保存p.next
		p.next = head		# 然后断开p与原链表，将p作为新链表的表头
		head = p			# 使head成为新链表的表头
		p = q				# 使p成为原链表表头

	return head

嗯，真的，简单了不止一点，也简洁了不止一点。
今天又是大聪明的一天捏。