python堆栈反转链表
时间: 2023-08-25 19:10:32 浏览: 132
要在Python中反转链表,可以使用堆栈的方式来实现。下面是一个示例代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverse_list(head):
stack = []
while head:
stack.append(head)
head = head.next
new_head = ListNode()
curr = new_head
while stack:
node = stack.pop()
curr.next = ListNode(node.val)
curr = curr.next
return new_head.next
```
你可以使用该代码来反转一个链表。首先,将链表节点依次压入堆栈中。然后,创建一个新的链表头部节点,并按照堆栈的顺序将节点连接起来。最后返回反转后的链表头部。
注意:这里创建了一个新的链表,并复制了原始链表节点的值。如果需要修改原始链表,请根据实际情况进行相应的修改。
相关问题
反转链表题解
### 反转链表的算法解析
反转链表是一种常见的算法问题,其核心在于改变链表中节点之间的指向关系。以下是基于 Python 和 Java 的两种实现方式。
#### 方法一:迭代法(Python 实现)
通过遍历原链表中的每一个节点,并逐步将其加入到新链表头部的方式完成反转操作。这种方法的时间复杂度为 O(n),空间复杂度为 O(1)[^1]。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
prev = None # 初始化前驱节点为空
curr = head # 当前节点初始化为头节点
while curr is not None: # 遍历整个链表直到当前节点为空
temp_next = curr.next # 暂存下一个节点
curr.next = prev # 将当前节点的下一指针指向之前的节点
prev = curr # 更新前驱节点为当前节点
curr = temp_next # 移动到下一个节点
return prev # 返回新的头节点
```
此方法的关键点在于每次都将 `curr` 节点的 `next` 指向它的前一个节点 `prev`,并不断更新这两个变量的位置[^5]。
---
#### 方法二:递归法(Java 实现)
递归的方法可以更简洁地表达逻辑,但需要注意栈溢出的风险。对于非常长的链表来说,可能会超出系统的堆栈容量。因此,在实际应用中需谨慎使用这种方案[^3]。
```java
public class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
// 如果到达最后一个节点或者列表为空,则直接返回该节点作为新的头节点
return head;
}
ListNode reversedHead = reverseList(head.next); // 对后续部分进行翻转后的子链表头
head.next.next = head; // 把当前层的下一层连接回自己形成反向链接
head.next = null; // 断开原来的正向链接防止环路产生
return reversedHead; // 返回最终的新头节点
}
}
```
这里采用的是自底向上构建的思想——先让后面的元素全部倒序排列好再逐级处理前面的部分直至整体完成转换过程[^4]。
---
#### 时间与空间复杂度分析
无论是哪种解决方案都只涉及单次扫描整个输入序列的操作流程故它们均具备线性的运行效率即O(N),其中N代表待处理的数据量大小;而额外使用的存储资源则取决于具体选用的技术路线前者无需开辟任何辅助结构因而只需常数级别的内存消耗(O(1))后者因为要保存每一层次调用的信息所以在最坏情况下可能达到跟原始对象规模相同的程度也就是O(N)[^2].
---
### 注意事项
当遇到边界情况比如空集或是只有一个成员构成的情形时应该特别留意确保程序能够妥善应对这些特殊状况以免引发异常行为或错误结果.
---
回文链表 力扣python
### 解决方案概述
为了判断单向链表是否为回文结构,可以采用多种方法来实现这一目标。一种常见的策略是通过反转一半的链表并比较两部分节点值的方式来进行验证[^1]。
### 方法一:使用列表存储前半部分链表
这种方法涉及遍历整个链表并将前半部分节点的值存入列表中,在访问到中间位置之后停止写入操作;随后继续遍历剩余部分并与之前保存下来的数值做对比,以此确认两者之间是否存在镜像关系。
```python
class Solution(object):
def isPalindrome(self, head):
vals = []
current_node = head
while current_node is not None:
vals.append(current_node.val)
current_node = current_node.next
return vals == vals[::-1]
```
此算法的时间复杂度为O(n),空间复杂度同样为O(n)[^3]。
### 方法二:双指针加栈辅助
该方法利用两个不同速度移动的指针(快慢指针),当较快的那个到达终点时较慢的一个正好位于中心附近的位置上。接着再创建一个新的指向头结点的临时变量用于后续处理,并将从当前位置起始直到结尾处的所有元素依次压入堆栈内。最后一步则是再次沿原路返回起点的同时不断弹出栈顶元素进行匹配检验直至完成全部检查工作为止。
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def isPalindrome(head: Optional[ListNode]) -> bool:
slow = fast = head
stack = []
# 使用快慢指针找到链表中点
while fast and fast.next:
stack.append(slow.val)
slow = slow.next
fast = fast.next.next
# 如果fast不为空,则说明链表长度为奇数,跳过最中间那个节点
if fast:
slow = slow.next
# 开始比较后半段与stack中的数据是否相等
while slow:
top_val = stack.pop()
if top_val != slow.val:
return False
slow = slow.next
return True
```
这段代码实现了更高效的内存利用率,因为只用了额外的空间去储存了一半的数据量,所以其时间复杂度仍保持在线性级别即O(n),而所需占用的工作区则减少到了大约原来的一半大小也就是O(n/2)[^2]。
阅读全文
相关推荐














