【Leetcode206】反转链表

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

• //输入：head = [1,2,3,4,5]
• //输出：[5,4,3,2,1]

思路

首先，我们定义了两个指针 prev 和 curr ，初始时将它们都指向链表的头节点 head 。然后，我们使用一个循环，遍历整个链表。

在每一次循环中，我们先将 curr 的下一个节点保存在 nextNode 中，以便在反转后能够继续遍历链表。然后，我们将 curr 的 next 指针指向 prev ，这样就将 curr 的指针方向反转了。接着，我们将 prev 指向当前节点 curr ， curr 指向下一个节点 nextNode ，继续下一次循环。

通过不断地反转指针的指向，最终我们可以将整个链表反转过来。最后，我们返回反转后的链表的头节点 prev 。

这个算法的时间复杂度为 O(n)，其中 n 是链表的长度，因为我们需要遍历整个链表一次来完成反转操作。

算法代码

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;

        while (curr != null) {
            ListNode nextNode = curr.next;
            curr.next = prev;
            prev = curr;
            curr = nextNode;

        }
        return prev;
    }
}