LeetCode206.Reverse Linked List反转链表(Python可运行，带测试用例)_手撕代码leetcode 206、反转链表python

一、题目

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

二、思路

双指针迭代法
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head
然后不断遍历 cur（cur指针往后走）
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
动画演示如下：

动画演示中其实省略了一个tmp变量，这个tmp变量会将cur的下一个节点保存起来

三、题解

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution(object):
	def reverseList(self, head):
		# 申请两个节点，pre和 cur，pre开始指向None
		pre = None
		# cur开始指向head
		cur = head
		# 遍历链表，最后cur变为空结束
		while cur:
			# 用tmp记录当前节点的下一个节点
			tmp = cur.next
			# 然后将当前节点指向pre
			cur.next = pre
			# pre和cur节点都前进一位
			pre = cur
			cur = tmp
		# 最后返回原来链表的尾部，就是反转后链表的头部
		return pre

# 构造链表
l1 = ListNode(1)    # 建立链表1->2->3->4->5->None
l1.next = ListNode(2)
l1.next.next = ListNode(3)
l1.next.next.next = ListNode(4)
l1.next.next.next.next = ListNode(5)

s = Solution()
l = s.reverseList(l1)
print (l.val, l.next.val, l.next.next.val, l.next.next.next.val, l.next.next.next.next.val)
# 5 4 3 2 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。

空间复杂度：O(1)。