目录
2024-03-11 leetcode写题记录
206. 反转链表
题目链接
题意
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解法
链表反转板子题，特殊处理下一个点都没有的情况就行。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
void f(ListNode* x, ListNode*& head) {
if (x == nullptr)
return;
if (x->next == nullptr) {
head = x;
return;
}
f(x->next, head);
x->next->next = x;
x->next = nullptr;
}
ListNode* reverseList(ListNode* head) {
f(head, head);
return head;
}
};
876. 链表的中间结点
题目链接
题意
给你单链表的头结点\(head\)，请你找出并返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
解法
快慢指针，时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* middleNode(ListNode* head) {
ListNode *l = head, *r = head;
while (l != nullptr && r != nullptr) {
if (r->next == nullptr)
return l;
l = l->next;
r = r->next->next;
}
return l;
}
};