设计一个算法实现链表翻转
时间: 2023-06-27 09:07:11 浏览: 56
链表翻转是一个经典的算法问题,可以使用迭代或递归两种方法来实现。这里我提供一种迭代的实现方法,具体步骤如下:
1. 定义三个指针 prev、curr 和 next,初始时 prev 和 curr 都指向 null,next 指向链表的第一个节点。
2. 循环遍历链表,每次将 curr 的 next 指针指向 prev,然后将 prev、curr、next 分别向后移动一位,直到 next 指向 null,此时 prev 指向原链表的最后一个节点,curr 指向 null,反转后的链表头节点为 prev。
下面是代码实现:
```
class ListNode {
int val;
ListNode next;
ListNode(int val) {
this.val = val;
}
}
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = null;
ListNode next = head;
while (next != null) {
curr = next;
next = next.next;
curr.next = prev;
prev = curr;
}
return prev;
}
```
时间复杂度为 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 ]
设计一个算法,通过遍历一趟,将链表中所有结点的链接标的目的逆转,仍利用原表 存储空间.
好的,这是一个关于数据结构的问题,可以进行回答。
对于这个问题,可以使用三个指针逐个翻转节点的链接。具体思路如下:
1.定义三个指针p,q,r,分别指向当前节点,前一个节点和后一个节点。
2.遍历整个链表,每次将当前节点的链接指向前一个节点,然后依次移动p、q、r指针向前。
3.最后将头节点的链接指向null,返回新的头节点。
代码实现如下:
```java
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode p = head;
ListNode q = null;
ListNode r = null;
while (p != null) {
r = p.next;
p.next = q;
q = p;
p = r;
}
head.next = null;
return q;
}
```