数据结构实现单链表反转
时间: 2023-11-26 21:02:35 浏览: 40
单链表反转可以通过遍历链表,将每个节点的指针指向其前驱节点来实现。具体实现步骤如下:
1. 定义三个指针:pre、cur、next,分别表示当前节点的前驱节点、当前节点和后继节点。
2. 将 cur 指向链表的头节点。
3. 遍历链表,每次循环执行以下操作:
- 将 next 指向 cur 的后继节点。
- 将 cur 的指针指向 pre。
- 将 pre 指向 cur。
- 将 cur 指向 next。
4. 遍历结束后,将链表的头节点指向 pre。
下面是单链表反转的 Python 代码实现:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseList(head: ListNode) -> ListNode:
pre, cur = None, head
while cur:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
```
相关问题
数据结构单链表的逆置
单链表的逆置有两种方法:头插法和递归法。头插法是将原链表的每个节点插入到新链表的头部,从而实现逆置;递归法则是将原链表分为当前表头结点和其余部分,递归的过程就是,先将表头结点从链表中拆出来,然后对其余部分进行逆序,最后将当前的表头结点链接到逆序链表的尾部。递归的终止条件就是链表只剩一个节点时,直接返回这个节点。
以下是两种方法的代码实现:
头插法:
```c
//单链表反转(头插法)
LIST* reverse(LIST* head) {
LIST *temp=NULL,*Phead=NULL;
while(head!=NULL) {
temp=head;
head=head->next;
temp->next=Phead;
Phead=temp;
}
return Phead;
}
```
递归法:
```c
//单链表反转(递归法)
LIST* reverse(LIST* head) {
if(head==NULL||head->next==NULL)
return head;
LIST *new_head=reverse(head->next);
head->next->next=head;
head->next=NULL;
return new_head;
}
```
单链表的逆置数据结构
单链表的逆置,也称为链表反转,是指改变一个单链表中节点的顺序,使得原来的头节点变成新的尾节点,而原来的尾节点变成新的头节点。在不使用额外存储空间的情况下,可以通过迭代或递归的方法来实现这个过程。
**迭代法**:
1. 定义两个指针,一个指向当前节点(prev),一个指向当前节点的后继(current)。
2. 指针current开始时指向头节点,然后每次移动,同时更新prev指向current,current指向current的下一个节点,直到current为null。
3. 当current为null时,prev即为新的头节点。
**递归法**:
1. 定义一个辅助函数,传入当前节点(current)和前一个节点(prev,初始为null)。
2. 如果current为null,则返回,否则递归调用函数,将current的next赋值给current,然后返回current。
3. 最后返回null作为新的头节点,此时链表已经反转。
**相关问题--:**
1. 迭代法和递归法在链表逆置中的优缺点是什么?
2. 如何在Java中实现单链表的逆置?
3. 链表逆置后,原来的头节点和尾节点如何确定?
相关推荐
![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)