反转一个链表
时间: 2023-06-28 17:09:10 浏览: 59
反转一个链表可以使用三个指针分别指向当前节点、前一个节点和后一个节点,然后依次进行反转。具体实现如下:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
ListNode* reverseList(ListNode* head) {
ListNode* pre = nullptr;
ListNode* cur = head;
while (cur != nullptr) {
ListNode* nxt = cur->next;
cur->next = pre;
pre = cur;
cur = nxt;
}
return pre;
}
```
这个算法的时间复杂度是 $O(n)$,其中 $n$ 是链表的长度。
相关问题
python 反转一个链表
可以使用多种方法来反转一个链表。一种方法是创建一个新的链表,遍历原始链表并将元素逐个插入到新链表的头部。可以使用一个数组来存储原始链表的元素,在从数组尾到头读取的过程中建立一个新的链表。这种方法的时间复杂度为O(n),空间复杂度为O(n)。代码如下所示<span class="em">1</span><span class="em">2</span><span class="em">3</span>
#### 引用[.reference_title]
- *1* [python 实现单链表翻转的几种常用方法](https://blog.csdn.net/neo_lcx/article/details/108082686)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *2* [python算法题 链表反转详解](https://download.csdn.net/download/weixin_38530846/14874139)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
- *3* [链表-翻转链表(python)](https://blog.csdn.net/weixin_44159202/article/details/131231577)[target="_blank" data-report-click={"spm":"1018.2226.3001.9630","extra":{"utm_source":"vip_chatgpt_common_search_pc_result","utm_medium":"distribute.pc_search_result.none-task-cask-2~all~insert_cask~default-1-null.142^v93^chatsearchT3_2"}}] [.reference_item style="max-width: 33.333333333333336%"]
[ .reference_list ]
python用栈反转一个链表
可以使用栈来反转一个链表的顺序。以下是用Python实现的示例代码:
```python
class Node:
def __init__(self, data):
self.data = data
self.next = None
def reverse_linked_list(head):
if not head:
return None
stack = []
current = head
while current:
stack.append(current)
current = current.next
# 弹出栈中的节点,改变指针方向
new_head = stack.pop()
current = new_head
while stack:
node = stack.pop()
current.next = node
current = node
current.next = None
return new_head
```
这里定义了一个简单的链表节点类 `Node`,其中 `data` 属性存储节点的数据,`next` 属性指向下一个节点。函数 `reverse_linked_list` 接受链表头节点作为参数,并使用一个栈来反转链表的顺序。先将链表中的所有节点按顺序入栈,再依次出栈并改变节点间的指针方向,最后返回新的头节点。
你可以使用以下代码来测试:
```python
# 创建链表:1 -> 2 -> 3 -> 4 -> 5
head = Node(1)
head.next = Node(2)
head.next.next = Node(3)
head.next.next.next = Node(4)
head.next.next.next.next = Node(5)
# 反转链表
new_head = reverse_linked_list(head)
# 遍历打印反转后的链表
current = new_head
while current:
print(current.data, end=' ')
current = current.next
```
输出结果为:`5 4 3 2 1`,表示链表成功反转。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)