单链表的逆序用代码表示
时间: 2023-05-30 09:03:38 浏览: 57
以下是单链表的逆序代码:
```python
class Node:
def __init__(self, val):
self.val = val
self.next = None
def reverseLinkedList(head):
prev = None
curr = head
while curr:
next_node = curr.next
curr.next = prev
prev = curr
curr = next_node
return prev
```
其中,`head`是链表的头节点。我们使用两个指针`prev`和`curr`,分别指向当前节点的前一个节点和当前节点。在循环中,我们先将`next_node`指向当前节点的下一个节点,然后将当前节点的`next`指向`prev`,再将`prev`指向当前节点,最后将`curr`指向`next_node`,这样就完成了一个节点的反转。最终返回的是新的头节点`prev`。
相关问题
数据结构如何实现单链表逆序,举个例子
实现单链表逆序有多种方法,其中一种比较常见的方法是采用迭代的方式进行逆序,具体实现步骤如下:
1. 定义三个指针pre、cur、next,分别表示当前节点的前一个节点、当前节点和当前节点的后一个节点。
2. 将cur指向链表的头节点,pre指向null。
3. 依次遍历链表中的每个节点,将cur的next指针指向pre。
4. 同时将pre、cur、next依次往后移动一个节点,继续遍历链表,直到cur指向最后一个节点。
5. 完成链表的逆序操作后,将链表的头节点指向cur节点。
下面是一个示例代码:
// 定义单链表节点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
// 实现单链表逆序
ListNode* reverseList(ListNode* head) {
ListNode* pre = NULL;
ListNode* cur = head;
ListNode* next = NULL;
while(cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
假设初始链表为:1 -> 2 -> 3 -> NULL,经过逆序操作后,链表变成:3 -> 2 -> 1 -> NULL。
用时间复杂度为n的算法,将一个长度为n的单链表逆序排列
可以使用迭代的方式对单链表进行逆序排列。具体步骤如下:
1. 定义三个指针,分别指向当前节点、前一个节点和后一个节点。
2. 将当前节点的 next 指针指向前一个节点。
3. 将前一个节点指针后移,指向当前节点。
4. 将当前节点指针后移,指向后一个节点。
5. 重复步骤2到4,直到当前节点为 null,表示已经遍历完整个链表。
6. 将链表的头节点指向前一个节点。
代码实现如下:
```java
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode next = curr.next;
curr.next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
时间复杂度为 O(n),空间复杂度为 O(1)。