反转链表
时间: 2023-06-28 09:07:59 浏览: 176
反转链表是指将链表中的元素顺序颠倒过来,例如将链表 1->2->3->4 反转为 4->3->2->1。这是一道经典的链表问题,通常有迭代和递归两种解法。
迭代解法:
从链表头节点开始遍历,每次将当前节点的 next 指针指向前一个节点,然后将前一个节点指针指向当前节点,最后将当前节点指向下一个节点。这样就能将链表逆序。
递归解法:
递归解法的思想是将链表分为头节点和剩余部分两部分,然后递归反转剩余部分,然后将头节点接到反转后的剩余部分的末尾即可。
以下是迭代解法的示例代码:
```python
def reverseList(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
以下是递归解法的示例代码:
```python
def reverseList(head):
if not head or not head.next:
return head
node = reverseList(head.next)
head.next.next = head
head.next = None
return node
```
相关问题
用python做反转链表,要求输入一个链表,反转链表后,输出链表的所有元素。
好的,这是一个编程问题,很高兴为你解答。下面是用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 = curr.next
curr.next = prev
prev = curr
curr = next
return prev
# 测试
head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))))
head = reverseList(head)
while head:
print(head.val)
head = head.next
# 输出:5 4 3 2 1
```
这段代码中,我们定义了一个`ListNode`类表示链表节点,其中包括一个值`val`和指向下一个节点的指针`next`;另外定义了一个函数`reverseList`,它接收一个链表头节点`head`,返回反转后的链表头节点。
具体实现方式是用两个指针`prev`和`curr`分别指向反转后的上一个节点和当前节点,然后遍历链表,依次修改节点的指针指向即可。
最后我们对反转后的链表进行遍历输出,验证反转结果是否正确。
python 反转链表
好的,以下是 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
```
这里使用了双指针的方法,prev 指向当前节点的前一个节点,curr 指向当前节点,next_node 指向当前节点的下一个节点。在遍历链表时,将 curr 的 next 指向 prev,然后将 prev 和 curr 向后移动一个节点,直到遍历完整个链表。
阅读全文