目录

• 2024-03-11 leetcode写题记录
  • 206. 反转链表
    • 题目链接
    • 题意
    • 解法
  • 876. 链表的中间结点
    • 题目链接
    • 题意
    • 解法

2024-03-11 leetcode写题记录

206. 反转链表

题目链接

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. 链表的中间结点

题目链接

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;
    }
};