介绍

一种解决方案是 按原始顺序迭代结点，并将它们逐个移动到列表的头部。

在该算法中，每个结点只移动一次。

因此，时间复杂度为 ，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为 。

题目

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

方案一（迭代）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return nil
    }
    var prev *ListNode
    node := head.Next
    head.Next = nil
    for node != nil {
        prev = node
        node = node.Next
        prev.Next = head
        head = prev
    }
    return head
}

• 移动指针的时候需要注意第一次移动要断掉 head 节点的指针

方案二（迭代）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var _head *ListNode
    var node *ListNode
    for head != nil {
        node = head
        head = head.Next
        node.Next = _head
        _head = node
    }
    return _head
}

• 与方案一不同的是，该方案一开始使用一个新的节点作为起点，而不是直接使用 head 节点；
• 注意赋值顺序。

方案三（递归）

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var _head *ListNode
    var moveToFront func(node *ListNode)
    moveToFront = func(node *ListNode) {
        if node == nil {
            return
        }
        prev := node
        node = node.Next
        prev.Next = _head
        _head = prev
        moveToFront(node)
    }
    moveToFront(head)
    return _head
}

原文

https://leetcode-cn.com/explore/learn/card/linked-list/195/classic-problems/749/