python写一个单链表逆序算法
时间: 2023-06-12 14:07:59 浏览: 57
以下是Python实现的单链表逆序算法:
```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:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
这里我们定义了一个`ListNode`类来表示链表中的节点,每个节点由一个值`val`和一个指向下一个节点的指针`next`组成。`reverseList`函数接收一个链表的头节点`head`作为输入,返回一个逆序后的链表的头节点。
我们使用三个指针`prev`、`curr`和`next_node`来完成链表的逆序。初始时,`prev`指向`None`,`curr`指向头节点`head`,`next_node`指向`curr`的下一个节点。在循环中,依次将`curr`的`next`指针指向`prev`,然后更新`prev`、`curr`和`next_node`的值。当`curr`为空时,循环结束,此时`prev`指向原链表的尾节点,即逆序后的链表的头节点。最后返回`prev`即可。
相关问题
用时间复杂度为n的算法,将一个长度为n的单链表逆序排列。
可以使用迭代法或递归法来实现单链表的逆序排列。
迭代法的实现思路是,依次将每个节点的 next 指针指向它的前驱节点。具体步骤如下:
1. 定义三个指针 prev、curr 和 next,分别指向当前节点的前驱节点、当前节点和当前节点的后继节点。
2. 遍历单链表,对于当前节点,将它的 next 指针指向它的前驱节点 prev,然后将 prev、curr 和 next 指针同时向右移动一个节点。
3. 当遍历到最后一个节点时,将它的 next 指针指向它的前驱节点 prev,并将它设为新的头节点。
代码如下:
```python
def reverseList(head):
if not head or not head.next:
return head
prev, curr, next = None, head, head.next
while curr:
curr.next = prev
prev = curr
curr = next
next = next.next if next else None
return prev
```
递归法的实现思路是,先递归地反转后续节点,然后将当前节点的 next 指针指向它的后继节点的后继节点。具体步骤如下:
1. 递归地反转当前节点后面的节点。
2. 将当前节点的 next 指针指向它的后继节点的后继节点。
3. 返回新的头节点。
代码如下:
```python
def reverseList(head):
if not head or not head.next:
return head
newHead = reverseList(head.next)
head.next.next = head
head.next = None
return newHead
```
这两种方法的时间复杂度均为 O(n),空间复杂度为 O(1)。
对于不带头结点的单链表L设计一个递归算法逆序输出所有结点
可以使用递归的方式逆序输出单链表的所有节点。具体的算法如下:
1. 如果链表为空,直接返回。
2. 递归输出链表的后继节点。
3. 输出当前节点的值。
代码实现如下:
```python
def reverse_output(node):
if node is None:
return
reverse_output(node.next)
print(node.value)
```
其中,`node` 表示当前节点,`node.next` 表示当前节点的后继节点。在递归输出后继节点之后,再输出当前节点的值,即可实现逆序输出单链表的所有节点。
需要注意的是,这种方法会使用系统栈保存递归过程中的所有节点,如果链表非常长,可能会导致栈溢出。因此,在实际应用中,需要根据链表的长度和系统栈的大小来选择是否使用递归算法。