单向链表反转java实现（java反转单链表 (三种方法整理)）

科技前沿 • 2025-05-23 14:49 • 阅读 39

大家好，我是讯享网，很高兴认识大家。

要反转链表中从位置 m 到 n 的部分，可以按以下步骤进行操作：

首先，找到第 m 个节点和第 n 个节点的位置。

讯享网

然后，我们将从第 m 个节点到第 n 个节点的部分链表进行反转操作。

最后，将反转后的部分链表重新连接到原链表中。

下面是具体的算法实现：

声明一个 dummy 节点，并将其 next 指针指向头节点。同时声明 pre 指针指向 dummy 节点。
将 pre 指针移动到第 m - 1 个节点的位置。
声明一个 cur 指针指向 pre 指针的下一个节点。
声明一个 tail 指针指向 cur 指针的下一个节点。
从 m 到 n 的位置进行反转操作，需要进行 n - m 次迭代。
1. 将 cur 指针的 next 指针指向 tail 指针。
2. 将 pre 指针的 next 指针指向 cur 指针。
3. 将 cur 指针移动到 tail 指针的位置。
4. 将 tail 指针指向 cur 指针的下一个节点。
将反转后的部分链表重新连接到原链表中，即将第 m - 1 个节点的 next 指针指向第 n 个节点。
返回 dummy 节点的 next 指针。

以下是具体的实现代码：

def reverseBetween(head, m, n): dummy = ListNode(0) dummy.next = head pre = dummy # 得到第 m - 1 个节点 for _ in range(m - 1): pre = pre.next cur = pre.next tail = cur.next # 反转从第 m 个节点到第 n 个节点的部分<em>链表</em> for _ in range(n - m): cur.next = tail.next tail.next = pre.next pre.next = tail tail = cur.next return dummy.next

讯享网

该算法的时间复杂度为 O(n - m)，其中 n 是链表的长度。

单向链表反转java实现（java反转单链表 (三种方法整理)）

相关推荐