【LeetCode-Apr-链表二】-Aet

Bingliaolong 2025-04-02 23:08 Aet | 隐藏边栏 | 抢沙发 | 7 0

文章评分 3 次，平均分 5.0 ：

LCR 141. 训练计划 IV

Question

Ans1

/**

* 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* trainningPlan(ListNode* l1, ListNode* l2) {

ListNode tmp(0);

ListNode* tail = &tmp;

while(l1 && l2) {

if (l1->val < l2->val) {

tail->next = l1;

l1 = l1->next;

} else {

tail->next = l2;

l2 = l2->next;

}

tail = tail->next;

}

tail->next = (l1) ? l1 : l2;

return tmp.next;

}

};

LCR 141. 训练计划 III

Question

Ans1

/**

* 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* trainningPlan(ListNode* head) {

ListNode* prev = nullptr;

ListNode* cur = head;

ListNode* next = nullptr;

while(cur) {

next = cur->next;

cur->next = prev;

prev = cur;

cur = next;

}

return prev;

}

};

Ans2

/**

* 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* reverseList(ListNode* head) {

return revcur(head, nullptr);

}

private:

ListNode* revcur(ListNode* cur, ListNode* prev) {

if (!cur) {

return prev;

}

ListNode* res = revcur(cur->next, cur);

cur->next = prev;

return res;

}

};

LCR 140. 训练计划 II

Question

Ans1

/**

* 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* trainingPlan(ListNode* head, int cnt) {

if (!head) {

return head;

}

int count = 0;

ListNode* cur = head;

while (cur) {

count++;

cur = cur->next;

}

count = count - cnt;

while (head && count) {

head = head->next;

count--;

}

return head;

}

};

LCR 136. 删除链表的节点

Question

Ans1

我的

/**

* 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* deleteNode(ListNode* head, int val) {

if (!head) {

return head;

}

if (head->val == val) {

return head->next;

}

ListNode* prev = nullptr;

ListNode* cur = head;

while(cur) {

if (cur->val == val) {

prev->next = cur->next;

break;

} else {

prev = cur;

cur = cur->next;

}

return head;

}

};

Ans2

单指针的方法，效果和Ans1差不多
1. 超过两个节点的情况，从第二个节点开始，看是不是目标，如果不是，prev才移动，这就让prev一直保存的是检测节点的前一个节点

/**

* 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* deleteNode(ListNode* head, int val) {

if (!head) {

return head;

}

if (head->val == val) {

return head->next;

}

ListNode* prev = head;

while(prev->next && prev->next->val != val) {

prev = prev->next;

}

if (prev->next) {

prev->next = prev->next->next;

}

return head;

}

};

Ans3

递归的方法，把问题交给自己的下一个节点出处理，认为处理后的结果就是自己正确的下一个节点

/**

* 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* deleteNode(ListNode* head, int val) {

if (!head) {

return head;

}

head->next = deleteNode(head->next, val);

return head->val == val ? head->next : head;

}

};

LCR 123. 图书整理 I

Question

Ans1

我的

/**

* 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:

vector<int> reverseBookList(ListNode* head) {

if (!head) {

return {};

}

ListNode* prev = nullptr;

ListNode* cur = head;

ListNode* next = nullptr;

while(cur) {

next = cur->next;

cur->next = prev;

prev = cur;

cur = next;

}

std::vector<int> res;

while(prev) {

res.emplace_back(prev->val);

prev = prev->next;

}

return res;

}

};

Ans2

使用栈来解决，但是效率不行，不如Ans1

/**

* 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:

vector<int> reverseBookList(ListNode* head) {

if (!head) {

return {};

}

std::stack<int> tmp;

while(head) {

tmp.push(head->val);

head = head->next;

}

std::vector<int> res;

while(!tmp.empty()) {

res.emplace_back(tmp.top());

tmp.pop();

}

return res;

}

};

Ans3

使用stl的反转vector的算法来处理，和Ans1差不多，比Ans2优

/**

* 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:

vector<int> reverseBookList(ListNode* head) {

if (!head) {

return {};

}

std::vector<int> res;

while(head) {

res.emplace_back(head->val);

head = head->next;

}

std::reverse(res.begin(), res.end());

return res;

}

};

Ans4

使用的递归的方式，速度和Ans1和Ans3差不多，但是这个方法占用内存最多

/**

* 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 {

private:

std::vector<int> res;

void reverse(ListNode* head) {

if (!head) {

return;

}

reverse(head->next);

res.emplace_back(head->val);

}

public:

vector<int> reverseBookList(ListNode* head) {

if (!head) {

return res;

}

reverse(head);

return res;

}

};

LCR 027. 回文链表

Question

Ans1

我的

/**

* 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:

bool isPalindrome(ListNode* head) {

ListNode* mid = get_mid(head);

ListNode* tmp = revser(mid);

while (head && tmp) {

if (head->val != tmp->val) {

return false;

}

head = head->next;

tmp = tmp->next;

}

return true;

}

private:

ListNode* revser(ListNode* head) {

ListNode* prev = nullptr;

ListNode* cur = head;

ListNode* next = nullptr;

while (cur) {

next = cur->next;

cur->next = prev;

prev = cur;

cur = next;

}

return prev;

}

ListNode* get_mid(ListNode* head) {

if (!head) {

return head;

}

ListNode* slow = head;

ListNode* fast = head;

while(slow && fast) {

slow = slow->next;

if (fast->next) {

fast = fast->next->next;

} else {

break;

}

return slow;

}

};

Ans2

使用数组的方法，效率不如Ans1

/**

* 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:

bool isPalindrome(ListNode* head) {

std::vector<int> vec;

while(head) {

vec.emplace_back(head->val);

head = head->next;

}

for (int i = 0, j = vec.size() - 1; i < j; ++i, --j) {

if (vec[i] != vec[j]) {

return false;

}

return true;

}

};

Ans3

这个方法，存在重复判断，虽能达到目的，但感觉不如前两个方案

/**

* 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:

bool isPalindrome(ListNode* head) {

if (!head) {

return false;

}

front_node = head;

return recursive_check(head);

}

private:

ListNode* front_node;

bool recursive_check(ListNode* cur) {

if (!cur) {

return true;

}

if (!recursive_check(cur->next)) {

return false;

}

if (cur->val != front_node->val) {

return false;

}

front_node = front_node->next;

return true;

}

};

LCR 024. 反转链表

Question

Ans1

我的

/**

* 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* reverseList(ListNode* head) {

ListNode* prev = nullptr;

ListNode* cur = head;

ListNode* next = nullptr;

while (cur) {

next = cur->next;

cur->next = prev;

prev = cur;

cur = next;

}

return prev;

}

};

Ans2

递归的方法，效率差不多

/**

* 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* reverseList(ListNode* head) {

return revcur(head, nullptr);

}

private:

ListNode* revcur(ListNode* cur, ListNode* prev) {

if (!cur) {

return prev;

}

ListNode* res = revcur(cur->next, cur);

cur->next = prev;

return res;

}

};

LCR 141. 训练计划 IV
Question
Ans1
LCR 141. 训练计划 III
Question
Ans1
Ans2
LCR 140. 训练计划 II
Question
Ans1
LCR 136. 删除链表的节点
Question
Ans1
Ans2
Ans3
LCR 123. 图书整理 I
Question
Ans1
Ans2
Ans3
Ans4
LCR 027. 回文链表
Question
Ans1
Ans2
Ans3
LCR 024. 反转链表
Question
Ans1
Ans2

本文为原创文章，版权归Aet所有，欢迎分享本文，转载请保留出处！

Bingliaolong 关注：0 粉丝：0 最后编辑于：2025-04-06

Everything will be better.

一	二	三	四	五	六	日
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30	31

LCR 141. 训练计划 IV

Question

Ans1

LCR 141. 训练计划 III

Question

Ans1

Ans2

LCR 140. 训练计划 II

Question

Ans1

LCR 136. 删除链表的节点

Question

Ans1

Ans2

Ans3

LCR 123. 图书整理 I

Question

Ans1

Ans2

Ans3

Ans4

LCR 027. 回文链表

Question

Ans1

Ans2

Ans3

LCR 024. 反转链表

Question

Ans1

Ans2

你可能也喜欢

热评文章

发表评论

标签云集