【Golang】题解 | #反转链表#

1. 原地反转

本质上，完成链表中节点的反转，只需要一步操作：把当前节点的下一个节点的下一个节点，置为当前节点

cur.next.next = cur

随之而来会产生两个的问题：

1. 已反转的链表从哪开始
2. 未反转的链表如何保存

所以可以把整个链表分为三部分：

• 当前执行反转的节点
• 已反转的链表
• 未反转的链表

为此引入三个指针：

• newHead，已反转链表的头部，其初始值为空，pHead 指向它即完成链表反转
• pHead，当前反转节点
• pNext，未反转链表的头部，保存 pHead 的下一个节点

再梳理一下，当链表反转，需要做如下几步操作：

1. 保存 pHead 的下一个节点，防止后续链表丢失
2. 将 pHead 指向 newHead，完成节点反转
3. 更新 newHead 为 pHead，将完成反转的节点加入链表
4. 更新 pHead，继续反转还未反转的链表

可根据上面思路下出代码：

func ReverseList( pHead *ListNode ) *ListNode {
    if pHead == nil || pHead.Next == nil{
        return pHead
    }
    var newHead *ListNode
    for pHead != nil {
        pNext := pHead.Next  // 保留未反转链表
        pHead.Next = newHead  // 节点反转
        newHead = pHead   // 更新已反转链表
        pHead = pNext   // 更新当前节点
    }
    return newHead
}

利用 GO 的平行赋值语法，可以简化为：

func ReverseList( pHead *ListNode ) *ListNode {
    if pHead == nil || pHead.Next == nil{
        return pHead
    }
    var newHead *ListNode
    for pHead != nil {
        pHead, pHead.Next, newHead = pHead.Next, newHead, pHead
    }
    return newHead
}