给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。Java
时间: 2024-06-04 21:14:09 浏览: 2
代码如下:
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode pre = null;
ListNode cur = head;
while (cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
相关问题
给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。
给定一个单链表的头结点pHead,可以使用三个指针变量进行链表反转:pre,cur和next。首先初始化pre为空,cur为pHead,next为cur的下一个节点。每次循环将cur的next指向pre,pre向后移动一个节点,cur向后移动一个节点,next向后移动一个节点。循环n次后,cur将成为新链表的表头。
代码如下:
```
ListNode* reverseList(ListNode* pHead) {
ListNode *pre = NULL, *cur = pHead, *next = NULL;
while (cur != NULL) {
next = cur->next;
cur->next = pre;
pre = cur;
cur = next;
}
return pre;
}
```
用c语言给定一个单链表的头结点pHead(该头节点是有值的,比如在下图,它的val是1),长度为n,反转该链表后,返回新链表的表头。 数据范围: 要求:空间复杂度 ,时间复杂度 。
以下是用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)。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![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)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)