LeetCode No.206 反转链表

最近一直在 LeetCode 上刷题来熟悉 Go 的语法,遇见一道很绕头的题分享一下

题目要求:反转一个单链表

题目示例:

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

题目解法:

func reverseList(head *ListNode) *ListNode {
    if head == nil || head.Next == nil {
        return head
    }
    res := reverseList(head.Next)
    head.Next.Next = head
    head.Next = nil
    return res
}

答案解析

初始状态时:
file

让我们迭代至 head 指向 4 时,res = 5 -> nil
我们要使 5 -> nil 变为 5 -> 4,则 head.Next.Next = head,即
file
此时明显可以看出 4和5 形成了一个环,则 head.Next = nil,即
file
此时可知当前返回后迭代至 head 指向 3res = 5 -> 4 -> nil
同样的根据上述流程可得
file
最终结果
file

讨论数量: 1

感觉 引入一个新 tmp 即可,做类似于栈的操作更容易理解点。
原链的 firstNode 作为 tmp 的 endNode 点 ,然后 头节点指向 tmp endNode节点。
下一节点 nextNode, tmp 头节点指向 nextNode, nextNode 指向 endNode
以此类推。

9个月前 评论

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!