每日一题 --- 反转链表[力扣][Go]

反转链表

题目：206. 反转链表

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

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
1
2

示例 2：

输入：head = [1,2]
输出：[2,1]
1
2

示例 3：

输入：head = []
输出：[]
1
2

提示：

• 链表中节点的数目范围是 [0, 5000]
• -5000 <= Node.val <= 5000

方法一：

创建一个新的空链表，然后扫描老链表节点，并将扫描到的结点使用头插法插入空链表，这样就得到了一个反转的链表。

func reverseList(head *ListNode) *ListNode {
   var newListNode *ListNode
   cur := head
   for cur != nil {
      newListNode = &ListNode{Val: cur.Val, Next: newListNode}
      cur = cur.Next
   }
   return newListNode
}
1
2
3
4
5
6
7
8
9

一个for循环，时间复杂度O(n)，用了额外的链表长度空间，空间复杂度O(n)。

方法二：

能不能让时间复杂度降为O(1)呢？反转链表不就是反转指针嘛，只要让指针指对了就行了。具体请看：[代码随想录](代码随想录 (programmercarl.com))
具体步骤如图：

func reverseList(head *ListNode) *ListNode {
   cur := head
   var pre *ListNode
   for cur != nil {
      temp := cur.Next
      cur.Next = pre
      pre = cur
      cur = temp
   }
   return pre
}
1
2
3
4
5
6
7
8
9
10
11

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