总结leetcode75中链表的算法题解题思路。
上一篇：力扣75——队列
以下代码大部分为本人所写，少部分为官方示例代码。
1 删除链表的中间节点
题目：
给你一个链表的头节点 head 。删除 链表的 中间节点 ，并返回修改后的链表的头节点 head 。
长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。
对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。
题解：前后指针。前指针指向最后一个个节点时，后指针指向了中间节点。
/**
* 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* deleteMiddle(ListNode* head) {
ListNode* beforep = head->next, *afterp = head, *prep = nullptr;
if (beforep == nullptr) return nullptr;
while (beforep!=nullptr) {
prep = afterp;
afterp = afterp->next;
beforep = beforep->next;
if (beforep != nullptr)
{
beforep = beforep->next;
}
}
prep->next = afterp->next;
return head;
}
};
2 奇偶链表
题目：
给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。
第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。
请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。
你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。
题解：双指针，分别指向奇数节点和偶数节点，然后再串起来。
/**
* 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* oddEvenList(ListNode* head) {
if (head == nullptr || head->next == nullptr) return head;
ListNode *ehead = head->next, *optr = head, *eptr = head->next;
while (true) {
if (eptr->next != nullptr) {
optr->next = eptr->next;
optr = optr->next;
}
else {
optr->next = nullptr;
break;
}
if (optr->next != nullptr) {
eptr->next = optr->next;
eptr = eptr->next;
}
else {
eptr->next = nullptr;
break;
}
}
optr->next = ehead;
return head;
}
};
3 反转链表
题目：
给你单链表的头节点 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:
ListNode* reverseList(ListNode* head) {
stack<ListNode*> st;
while (head) {
st.push(head);
head = head->next;
}
ListNode *tmp = new ListNode(0);
head = tmp;
while (!st.empty()) {
tmp->next = st.top();
tmp = tmp->next;
st.pop();
}
tmp->next = nullptr;
return head->next;
}
};
4 链表最大孪生和
题目：
在一个大小为 n 且 n 为 偶数 的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点 。
比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。
孪生和 定义为一个节点和它孪生节点两者值之和。
给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。
题解：先用前后指针，找到中间节点，然后反转链表的后半截，再遍历逐一求和。文章来源：https://www.toymoban.com/news/detail-618704.html
/**
* 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:
int pairSum(ListNode* head) {
ListNode* slow = head;
ListNode* fast = head->next;
while (fast->next) {
slow = slow->next;
fast = fast->next->next;
}
// 反转链表
ListNode* last = slow->next;
while (last->next) {
ListNode* cur = last->next;
last->next = cur->next;
cur->next = slow->next;
slow->next = cur;
}
int ans = 0;
ListNode* x = head;
ListNode* y = slow->next;
while (y) {
ans = max(ans, x->val + y->val);
x = x->next;
y = y->next;
}
return ans;
}
};
1-4 解题总结
得用指针来索引遍历。
常用方法：前后指针。文章来源地址https://www.toymoban.com/news/detail-618704.html
到了这里，关于力扣75——链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
