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
}