题目描述

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

解题思路

第一反应是递归，拿到一个链表，取出头节点，反转剩余节点的链表，然后把当前节点加到反转后的链表的尾部。递归的终止条件是当前节点为空，返回空指针。

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverse(head *ListNode) (*ListNode, *ListNode) {
    if head == nil {
        return nil, nil
    }

    if head.Next == nil {
        return head, head
    }

    start, tail := reverse(head.Next)
    tail.Next = head
    head.Next = nil

    return start, head
}

func reverseList(head *ListNode) *ListNode {
    start, _ := reverse(head)
    return start
}

这里要注意几点：

  1. 需要手动把末尾节点的 Next 指针置为 nil，否则会导致链表循环。
  2. 需要返回反转后的链表的头节点和尾节点，方便后续操作。
  3. 递归的时间复杂度是 O(n)，空间复杂度是 O(n)，因为递归调用栈的深度为 n。

继续思考，其实反转后不一定需要返回头节点和尾节点，只需要返回头节点就可以了，因为反转后的尾节点就是反转前的头节点。这样就可以简化代码，直接返回头节点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }

    newHead := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil

    return newHead
}

因为递归调用栈的深度为 n，所以这个方法的空间复杂度是 O(n)。但是如果链表的长度很大，递归调用栈的深度会很大，可能会导致栈溢出。考虑使用迭代的方法来解决这个问题。

这里的思路就是，每次断开当前节点和下一个节点的连接，把当前节点放到反转后的链表的头部，然后继续遍历下一个节点。这样就可以在 O(n) 的时间复杂度内完成链表的反转，空间复杂度是 O(1)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) (res *ListNode) {
	for head != nil {
		next := head.Next
		head.Next = res
		res = head
		head = next
	}

	return
}