[LeetCode 笔记] 206. Reverse Linked List

前言

　　这是一题单向链结串列反转的题目，运用指标的算法，目标是将原本的链结串列倒序排列，此演算有使用到一个 while 迴圈，则时间複杂度估 O(n)，这里有 JAVA 和 Python 的写法。

题目

Given the head of a singly linked list, reverse the list, and return the reversed list.

给定一个 head 单向链结串列，反转这个串列，且回传反转过后的这个串列。

题目连结：https://leetcode.com/problems/reverse-linked-list/description/

题目限制

The number of nodes in the list is the range [0, 5000].
5000 <= Node.val <= 5000

範例

Input: head = [1,2,3,4,5]Output: [5,4,3,2,1]

Input: head = [1,2]Output: [2,1]

Input: head = []Output: []

思路&笔记

链结串列的题目，简单想像是在处理节点的位置，资料先放一边别去里他。
这里设定三个指标分别是指向 null 的 (指标一)、指向当前 head 的 (指标二)、辅助指标 nextNode (指标三)。

设定好三个指标后把当前的 curr.next 挂在辅助指标 nextNode 上 (确保在反转的过程中不会失去原始下一个节点的位置)挂完之后把当前节点 curr.next 指向 prev (此时指针已反转了)接下来移动指针 prev 到 curr将 curr 挂在 nextNode (刚刚保存的原始下一个节点的位置)以上逻辑循环到最后，当 curr 移动到 null 时则停止迴圈 (链结串列的末端节点一定会指向 null)

[补充] curr.next 同等于 curr → link (指向下一个节点的意思)

JAVA 实现

class Solution {    public ListNode reverseList(ListNode head) {        ListNode curr = head; // 当前指标 (指标一)        ListNode prev = null; // 空集合指标 (指标二)        // 检查确定链结串列里有资料        while (curr != null) {            ListNode nextNode = curr.next; // 辅助指标 (指标三)，指向下一个节点 (资料暂存在辅助指标内)            curr.next = prev; // 将 curr 的 next 指针指向 prev，(将当前节点的指针方向反转)            prev = curr; // 更新指针指向：将 prev 设为 curr            curr = nextNode; // curr 设为 nextNode        }        return prev;    }}

Python 实现

使用了和 Java 一样的逻辑执行，换成 Python 的写法。
(Python 中不需要再宣告一个额外的变数来存储原始的链结串列)

class Solution:    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:        prev = None # 空集合指标 (指标一)        while head:            nextNode = head.next # 辅助指标 (指标二)            head.next = prev # 反转            prev = head # 移动指标            head = nextNode # 挂回去原本的链结串列        return prev

成绩

(新手上路，如有错误请友善告知，感谢)

Blog
https://chris81051.github.io/2023/06/29/LeetCode-206-Reverse-Linked-List-Java-Python/
有分享技术文章、科技新闻、日常生活，欢迎一起讨论