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

时间:2024-03-28 08:05:05

反转链表

题目:206. 反转链表

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

示例 1:

img

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

示例 2:

img

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

示例 3:

输入:head = []
输出:[]

提示:

  • 链表中节点的数目范围是 [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
}

一个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
}

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