反转链表
时间: 2023-06-28 18:07:59 浏览: 71
反转链表是指将链表中的元素顺序颠倒过来,例如将链表 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
```
相关问题
反转链表java
反转链表是指将一个单向链表的每个节点的指向反转,即原来指向下一个节点的指针变成指向前一个节点。下面是反转链表的Java代码实现:
```java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode temp = curr.next;
curr.next = prev;
prev = curr;
curr = temp;
}
return prev;
}
```
在这个代码中,我们使用了三个指针,分别指向当前节点(curr)、前一个节点(prev)和后一个节点(temp)。我们每次将当前节点的指针指向前一个节点,然后依次移动三个指针即可。最后返回反转后的头节点(即原来的尾节点)。
需要注意的是,在反转链表时,一定要先将当前节点的next指针保存到一个临时变量中,否则在修改指针时会造成链表的断裂。
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 向后移动一个节点,直到遍历完整个链表。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)