☆打卡算法☆LeetCode 206. 反转链表 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定单链表的头结点，返回反转后的链表。”

题目链接：

来源：力扣（LeetCode）

链接： 206. 反转链表 - 力扣（LeetCode）

2、题目描述

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

示例 1：
输入： head = [1,2,3,4,5]
输出： [5,4,3,2,1]

示例 2：
输入： head = [1,2]
输出： [2,1]

二、解题

1、思路分析

题意要反转链表，返回反转后的链表。

只需要遍历整个链表，然后将当前节点改为指向前一个节点，遍历操作结束就完成了反转。

其中有一个问题，由于节点没有引用前一个节点，需要先存储前一个节点。

在更改引用之前，还需要存储后一个节点，最后才返回新的链表。

2、代码实现

代码参考：

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while (curr != null) {
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

3、时间复杂度

时间复杂度：O(n)

其中n是链表的长度，需要遍历链表一次。

空间复杂度：O(1)

只需要常数级的变量空间。

三、总结

1、定义两个指针： prepre 和 curcur ；prepre 在前 curcur 在后。 2、每次让 prepre 的 nextnext 指向 curcur ，实现一次局部反转 3、局部反转完成之后，prepre 和 curcur 同时往前移动一个位置 4、循环上述过程，直至 prepre 到达链表尾部