编写一段代码,实现这个功能:给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 0≤n≤1000 要求:空间复杂度 O(1),时间复杂度 O(n)
时间: 2023-02-09 14:52:47 浏览: 66
下面是一个可以实现这个功能的代码:
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(nullptr) {}
};
ListNode* reverseList(ListNode* pHead) {
// 特判,如果链表为空或者只有一个节点,直接返回
if (pHead == nullptr || pHead->next == nullptr) {
return pHead;
}
// 定义三个指针,分别指向当前节点、前一个节点和后一个节点
ListNode* pCur = pHead;
ListNode* pPrev = nullptr;
ListNode* pNext = pCur->next;
// 遍历链表,将当前节点的指针指向前一个节点,同时将前一个节点和后一个节点向后移动
while (pCur != nullptr) {
pCur->next = pPrev;
pPrev = pCur;
pCur = pNext;
if (pNext != nullptr) {
pNext = pNext->next;
}
}
// 返回反转后的链表头结点
return pPrev;
}
```
在这段代码中,我们定义了一个叫做 `ListNode` 的结构体,表示单链表的节点。在函数 `reverseList` 中,我们定义了三个指针,分别指向当前节点、前一个节点和后一个节点。我们使用一个循环来遍历链表,并在每一步将当前节点的指针指向前一个节点,同时将前一个节点和后一个节点向后移动。最后,我们返回反转后的链