LeetCode 206. 反转链表

codechangeworld-go / 2023-05-05 / 原文

题目链接：LeetCode 206. 反转链表
本题是链表题目中非常重要的一道题目--反转指针。
解题方法有两种：1.双指针法 2. 递归法
首先看双指针法：
快指针总是在慢指针的前面，也就是每次将快指针的节点的next指针更新成指向慢指针，这样不就进行了反转嘛。

完整代码如下：

func reverseList(head *ListNode) *ListNode {
    // 双指针法
    var pre *ListNode //慢指针
    curr:=head  //快指针
    for ;curr!=nil;{  //注意循环退出的条件，一定要反转所有的节点，
        temp:=curr.Next //记录当前节点的下一个节点（即下一个要反转的节点）
        curr.Next = pre  //反转指针
        pre = curr  //慢指针更新为当前节点
        curr = temp  //快指针更新为下一个要反转的节点
    }
    return pre
}

递归法：
本题的递归法与双指针法思路基本一致，按照递归三部曲：递归的参数、递归结束的条件、递归的单层逻辑进行
完整代码如下：

func reverseList(head *ListNode) *ListNode {
    // 递归法
    // var pre *ListNode  和双指针一样的逻辑，递归的参数是pre 和 curr
    //     curr:=head
    return reverse(nil, head)
}

func reverse(pre, head *ListNode)*ListNode{
    if head == nil {   //递归退出的条件
        return pre
    }
    // 递归中，单层的逻辑
    next := head.Next  //记录当前节点的下一个节点（即下一个要反转的节点）
    head.Next = pre  //反转指针
    return reverse(head, next)  //进行递归
}