本文由简悦 SimpRead 转码，原文地址 programmercarl.com

题意：

反转一个单链表。
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。//递归
funcreverseList(head ListNode) ListNode {
// 如head为5，5的下一个为nil，就终止循环
if head == nil || head.Next == nil {
return head
}
// 先进入到里层，也就是链表5直接返回5，开始处理下面的程序，往回撤
newHead := reverseList(head.Next)
// 开始逆置链表指针
head.Next.Next = head //4的下一个是5，5的下一个改为4
head.Next = nil// 将原先的链表顺序指向为nil：将4的下一个指向nil
// fmt.Printf(“newHead=%+v\n”, newHead) // 四次打印，全部都是： newHead=&{Val:5 Next:0xc000010380}
return newHead // 函数的返回值是ListNode
}代

示例 1：

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

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

思路

如果再定义一个新的链表，实现链表元素的反转，其实这是对内存空间的浪费。

其实只需要改变链表的 next 指针的指向，直接将链表反转，而不用重新定义一个新的链表，如图所示:

反转链表 - 图2

之前链表的头节点是元素 1，反转之后头结点就是元素 5 ，这里并没有添加或者删除节点，仅仅是改变 next 指针的方向。

迭代：双指针法

我们拿有示例中的链表来举例，如动画所示：
反转链表 - 图3
首先定义一个 cur 指针，指向头结点，再定义一个 pre 指针，初始化为 null。

然后就要开始反转了，首先要把 cur->next 保存一下

为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将 cur->next 指向 pre ，此时已经反转了第一个节点了。

接下来，就是循环走如下代码逻辑了，继续移动 pre 和 cur 指针。

最后，cur 指针已经指向了 null，循环结束，链表也反转完毕了。此时我们 return pre 指针就可以了，pre 指针就指向了新的头结点。

代码

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
 // 双指针法
func reverseList(head *ListNode) *ListNode {
    // 申明指针使用var，没有=号
    var pre *ListNode // 申明一个pre指针,类型为ListNode结构体的引用;默认值为nil；为上一个节点
    // &取值 ，默认值为结构体的初始化值
    // pre := &ListNode{} // pre={"Val": 0,"Next": null }
    cur := head // 申明cur指针，初始值为head头结点；为当前节点
    for cur != nil {
        next := cur.Next // 1 先保存下个节点
        cur.Next = pre // 2 翻转节点，将当前节点的下一个节点指向上一个节点
        pre = cur // 3 让上一个节点等于当前节点
        cur = next // 4 恢复刚开始保存的下一个节点，为当前节点，进行下一次循环
    }
    return pre // pre为ListNode节点的引用，最后的结果
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要遍历链表一次。
空间复杂度：O(1)。
递归法

代码

// 如链表为1->2->3->4->5

//递归
func reverseList(head *ListNode) *ListNode {
    // 如head为5，5的下一个为nil，就终止循环
    if head == nil || head.Next == nil {
        return head
    }
    // 先进入到里层，也就是链表5直接返回5，开始处理下面的程序，往回撤
    newHead := reverseList(head.Next)

    // 开始逆置链表指针
    head.Next.Next = head //4的下一个是5，5的下一个改为4
    head.Next = nil // 将原先的链表顺序指向为nil：将4的下一个指向nil
    return newHead // newHead = head
}

递归代码分析

// 递归
// 如链表为1->2->3->4->5
// 第一次入栈 head为1
func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    // 第2次入栈  head为2
    newHead := func reverseList(head.Next) *ListNode {
            if head == nil || head.Next == nil {
                return head
            }
            // 第3次入栈  head为3
            newHead := func reverseList(head.Next) *ListNode {
                    if head == nil || head.Next == nil {
                        return head
                    }
                    // 第4次入栈  head为4
                    newHead := func reverseList(head.Next) *ListNode {
                            if head == nil || head.Next == nil {
                                return head
                            }
                            // 第5次入栈  head为5
                            newHead := func reverseList(head.Next) *ListNode {
                                    // 第一轮出栈: head为5，head.next为空，返回head，此时head只有5；newHead=head=5
                                    if head == nil || head.Next == nil {
                                        return head
                                    }
                                }
                        // 第二轮出栈
                        // head为4，head.next为5，执行head.next.next=head也就是5.next=4，
                        head.Next.Next = head // 此时链表为1->2->3->4<->5
                        // 由于4与5互相指向，所以此处要断开4.next=null
                        head.Next = nil // 此时链表为1->2->3->4<-5
                        // newHead=head=5->4
                        return newHead
                    }
                //第三轮出栈
                // head为3，head.next为4，执行head.next.next=head也就是4.next=3，
                head.Next.Next = head // 此时链表为1->2->3<->4<-5
                // 由于3与4互相指向，所以此处要断开3.next=null
                head.Next = nil // 此时链表为1->2->3<-4<-5
                // newHead=head=5->4->3
                return newHead
            }
        //第四轮出栈
        // head为2，head.next为3，执行head.next.next=head也就是3.next=2，
        head.Next.Next = head // 此时链表为1->2<->3<-4<-5
        // 由于2与3互相指向，所以此处要断开2.next=null
        head.Next = nil // 此时链表为1->2<-3<-4<-5
        // newHead=head=5->4->3->2
        return newHead
    }
    // 第五轮出栈
    // head为1，head.next为2，执行head.next.next=head也就是2.next=1，
    head.Next.Next = head // 此时链表为1<->2<-3<-4<-5
    // 由于1与2互相指向，所以此处要断开1.next=null
    head.Next = nil // 此时链表为1<-2<-3<-4<-5
    // newHead=head=5->4->3->2->1
    return newHead
}

打印返回的NewHead

//递归
func reverseList(head *ListNode) *ListNode {
    // 如head为5，5的下一个为nil，就终止循环
    if head == nil || head.Next == nil {
        return head
    }
    // 先进入到里层，也就是链表5直接返回5，开始处理下面的程序，往回撤
    newHead := reverseList(head.Next)

    // 开始逆置链表指针
    head.Next.Next = head //4的下一个是5，5的下一个改为4
    head.Next = nil // 将原先的链表顺序指向为nil：将4的下一个指向nil

    //fmt.Printf("newHead=%+v\n", newHead.Next)  //只能显示一级 newHead=&{Val:5 Next:0xc000010380}

    // 打印结构化的结构体；
    bs, _ := json.Marshal(newHead)
    var out bytes.Buffer
    json.Indent(&out, bs, "", "\t")
    fmt.Printf("newHead=%v\n", out.String())

    return newHead // 函数的返回值是ListNode
}

复杂度分析

时间复杂度：O(n)，其中 n 是链表的长度。需要对链表的每个节点进行反转操作。

空间复杂度：O(n)，其中 n 是链表的长度。空间复杂度主要取决于递归调用的栈空间，最多为 n 层。

反转链表

题意：

思路

迭代：双指针法

代码

复杂度分析

递归法

代码

递归代码分析

打印返回的NewHead

复杂度分析