题目：反转链表

解题思路：迭代

  1. 创建两个指针，一个前置指针pre，为Null，一个当前节点指针cur，指向head
  2. 创建临时变量存当前节点的后续节点
  3. 将当前节点cur指针的next指向pre
  4. pre和cur指针向前移动
  5. 当cur指向为空则结束，返回反转链表pre

链表 - 图1

  1. def test(head):
  2.     # 创建两个节点pre，cur
  3.     pre, cur = None, head
  4.     # cur为空则结束循环
  5.     while cur:
  6.         # 临时变量存当前节点的后驱节点
  7.         temp = cur.next
  8.         # cur的next指向pre
  9.         cur.next = pre
  10.         #pre、cur指针向后移动
  11.         pre = cur
  12.         cur = temp
  13.     return pre
  • 时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
  • 空间复杂度：O(1)。