用c语言给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 要求:空间复杂度 ,时间复杂度 。
时间: 2023-05-21 08:06:44 浏览: 144
C语言单链表的实现
以下是用C语言实现反转单链表的代码:
```c
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* reverseList(struct ListNode* head) {
struct ListNode *prev = NULL;
struct ListNode *curr = head;
while(curr != NULL) {
struct ListNode *next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
return prev;
}
```
在该代码中,我们定义了一个结构体 `ListNode` 来表示单链表的每个节点,每个节点有一个整型值 `val` 和一个指向下一个节点的指针 `next`。函数 `reverseList` 用来反转整个链表,它输入链表的头节点 `head`,输出反转后的链表头节点。该函数的实现过程如下:
定义两个指针 `prev` 和 `curr`,分别指向反转后的链表头节点和当前节点。
遍历原链表,每次将当前节点 `curr` 的指针指向前一个节点 `prev`,然后将两个指针都向后移动一位。这样,反转后的链表就被构建出来了。
最后返回 `prev`,即反转后的链表头节点。
时间复杂度为 O(n),空间复杂度为 O(1)。
阅读全文