逆置带表头结点的单链表算法 python
时间: 2024-05-28 13:07:14 浏览: 15
逆置带头结点的单链表的算法可以通过遍历链表,将节点的next指针指向前一个节点实现。具体实现可以参考以下代码:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def reverseLinkedList(head: ListNode) -> ListNode:
prev = None
curr = head.next
while curr:
nxt = curr.next
curr.next = prev
prev = curr
curr = nxt
head.next = prev
return head
```
在这个算法中,我们创建了一个虚拟头结点来简化链表逆置的实现。我们将prev初始化为None,curr初始化为头结点的下一个节点。然后,我们遍历链表,依次将curr节点的next指针指向prev,然后更新prev和curr节点。最后,我们将头结点的next指针指向逆置后的链表的头节点prev,返回头结点即可。
相关问题
逆置带表头结点的单链表算法
逆置带表头结点的单链表算法可以用三个指针分别指向当前结点、它的前驱结点和后继结点,然后通过遍历链表来逆置每个结点的指针方向。
具体步骤如下:
1. 定义三个指针:preNode, curNode, nextNode,分别指向前驱结点、当前结点和后继结点。
2. 初始化 preNode 为 NULL,curNode 为头结点,nextNode 为头结点的下一个结点。
3. 遍历链表,直到 curNode 为 NULL。在每次循环中,将 curNode 的 next 指针指向 preNode,然后依次向后移动指针,即:preNode = curNode, curNode = nextNode, nextNode = nextNode->next。
4. 最后将头结点的 next 指针指向 preNode,即为逆置后的链表。
下面是实现代码:
```c++
void reverseList(ListNode* head) {
ListNode *preNode = NULL;
ListNode *curNode = head->next;
ListNode *nextNode = head->next;
while (curNode) {
nextNode = nextNode->next;
curNode->next = preNode;
preNode = curNode;
curNode = nextNode;
}
head->next = preNode;
}
```
带表头结点单链表的逆置
对于带头结点的单链表,我们可以从头结点的下一个节点开始,依次将每个节点插入到头结点之后,直到所有节点都被插入完成,最后再将头结点的next指针指向新的第一个节点即可。
具体实现如下:
```c++
void reverseList(ListNode* head) {
if (head == nullptr || head->next == nullptr) {
return;
}
ListNode* p = head->next;
ListNode* q = p->next;
while (q != nullptr) {
p->next = q->next;
q->next = head->next;
head->next = q;
q = p->next;
}
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)