C++ 反转链表II
时间: 2024-01-11 16:18:45 浏览: 30
好的,以下是 C++ 反转链表 II 的代码实现:
```c++
ListNode* reverseBetween(ListNode* head, int m, int n) {
if (!head || !head->next || m == n) return head;
ListNode *dummy = new ListNode(-1);
dummy->next = head;
ListNode *pre = dummy;
for (int i = 1; i < m; ++i) pre = pre->next;
ListNode *cur = pre->next;
for (int i = m; i < n; ++i) {
ListNode *t = cur->next;
cur->next = t->next;
t->next = pre->next;
pre->next = t;
}
return dummy->next;
}
```
相关问题
c++ 反转链表 完整程序
反转链表是指将链表中的节点顺序颠倒过来。下面是一个完整的C语言程序实现反转链表的功能:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义链表节点的结构体
typedef struct Node {
int data;
struct Node* next;
} Node;
// 创建一个新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
if (newNode == NULL) {
printf("内存分配失败\n");
exit(1);
}
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// 反转链表
Node* reverseList(Node* head) {
if (head == NULL || head->next == NULL) {
return head;
}
Node* prev = NULL; // 用于指向当前节点的前一个节点
Node* curr = head; // 当前节点
while (curr != NULL) {
Node* next = curr->next; // 保存当前节点的下一个节点
curr->next = prev; // 将当前节点指向前一个节点
prev = curr; // 更新前一个节点为当前节点
curr = next; // 更新当前节点为下一个节点
}
return prev; // 返回反转后的头节点
}
// 打印链表
void printList(Node* head) {
Node* curr = head;
while (curr != NULL) {
printf("%d ", curr->data);
curr = curr->next;
}
printf("\n");
}
int main() {
Node* head = createNode(1);
Node* node2 = createNode(2);
Node* node3 = createNode(3);
Node* node4 = createNode(4);
head->next = node2;
node2->next = node3;
node3->next = node4;
printf("原始链表: ");
printList(head);
Node* reversedHead = reverseList(head);
printf("反转后的链表: ");
printList(reversedHead);
return 0;
}
```
以上是一个反转链表的完整程序。程序中定义了一个节点结构体Node,然后实现了创建节点、反转链表、打印链表等功能函数。在主函数中,创建了一个包含4个节点的链表,并打印出原始链表和反转后的链表。
c++反转链表pat
以下是使用C++实现反转链表的代码,可以用于PAT等面试/编程练习。
```c++
#include <iostream>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode(int x) : val(x), next(NULL) {}
};
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;
}
int main() {
// 构造链表 1->2->3->4->5
ListNode* head = new ListNode(1);
head->next = new ListNode(2);
head->next->next = new ListNode(3);
head->next->next->next = new ListNode(4);
head->next->next->next->next = new ListNode(5);
// 反转链表
ListNode* newHead = reverseList(head);
// 输出反转后的链表
while (newHead != NULL) {
cout << newHead->val << ' ';
newHead = newHead->next;
}
cout << endl;
return 0;
}
```
输出结果为:
```
5 4 3 2 1
```
其中,`reverseList` 函数实现了链表的反转,使用了三个指针,分别指向当前节点、前一个节点和后一个节点。在循环中不断更新这三个指针,直到遍历完整个链表。
在 `main` 函数中,我们构造了一个链表,并调用 `reverseList` 函数将其反转,然后输出反转后的链表。