LeetCode.206 反转链表-一一网

这是我参与8月更文挑战的第9天，活动详情查看：8月更文挑战

题目描述：

206. 反转链表 – 力扣（LeetCode） (leetcode-cn.com)

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例一

输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]
复制代码

示例二

输入： head = [1,2]
输出： [2,1]
复制代码

示例三

输入： head = []
输出： []
复制代码

提示：

链表中节点的数目范围是 [0, 5000]
-5000 <= Node.val <= 5000

思路分析

迭代

链表有指向，反转只要把指向反过来就可以了。

我们只要记录下当前节点，前一个节点和后一个节点就行了，把当前节点的 next 指向当前节点的前一个节点

定义两个指针 pre 和 cur
pre 最初指向 null 因为第一个节点没有前节点
每次迭代 cur 的 next 指向 pre

AC代码

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        var prev: ListNode? = null
        var curr: ListNode? = head
        var next: ListNode? = null
        while (curr != null) {
            next = curr.next
            curr.next = prev
            prev = curr
            curr = next
        }
        return prev
    }
}

复制代码

递归

使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 prefix
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点
让当前结点的 next 指针指向 null ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。

AC代码

class Solution {
    fun reverseList(head: ListNode?): ListNode? {
        if(null == head || null == head.next){
            return head
        }
        val prefix = reverseList(head.next)
        head.next.next = head
        head.next = null
        return prefix
    }
}
复制代码