206. 反转链表 - 力扣（LeetCode）
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
解题思路
三指针。temp指针用于存储当前节点的下一节点，pre指针用于存储当前节点反转后指向的新节点。具体操作如下：
反转过程：
代码实现
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head || !head->next){
return head;
}
ListNode *pre = NULL;
ListNode *cur = head;
ListNode *tmp;
while(cur){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
return pre;
}
};24. 两两交换链表中的节点 - 力扣（LeetCode）
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
解题思路
递归。题干中的意思是对链表中的节点每两个进行互换，那么我们可以把前两个进行互换，后边剩余的视为一个整体，放入到下一层递归中。具体操作如下：
代码实现
class Solution {
public:
ListNode* swapPairs(ListNode* head) {
if(!head||!head->next){
return head;
}
ListNode *cur=head, *next=head->next;
ListNode *nextNext = swapPairs(next->next);
cur->next = nextNext;
next->next = cur;
return next;
}
};25. K 个一组翻转链表 - 力扣（LeetCode）
给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
解题思路
其实就是上边两道题结合起来，话不多说，直接上代码。
代码实现
class Solution {
public:
ListNode* reverseKGroup(ListNode* head, int k) {
if(!head || k == 1){
return head;
}
ListNode *cur = head;
// 1、先判断是否为最后部分（是则直接返回head保持原有顺序）
for(int i = 0; i < k; i++){
if(!cur){
return head;
}
cur = cur->next;
}
// 2、翻转k-1个指针
cur = head;
ListNode *pre = nullptr, *tmp = nullptr;
for(int i = 0; i < k; i++){
tmp = cur->next;
cur->next = pre;
pre = cur;
cur = tmp;
}
// 3、反转后和原链表进行连接
head->next = reverseKGroup(cur, k);
return pre;
}
};LCR 154. 复杂链表的复制 - 力扣（LeetCode）
请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
解题思路
迭代+拆分。首先将复制链表中的每个节点，插入到原链表中；随后，将旧节点的random指向传递给新的节点，最后拆分新旧链表，具体操作如下：
代码实现
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head){
return head;
}
Node *cur = head;
// 1、复制链表中的每个节点
while(cur){
Node *tmp = new Node(cur->val);
tmp->next = cur->next;
cur->next = tmp;
cur = tmp->next;
}
// 2、将旧节点的random指向传递给新的节点
cur = head;
while(cur){
if(cur->random){
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
// 3、拆分链表
cur = head->next;
Node *pre = head, *res = head->next;
while(cur->next){
pre->next = pre->next->next;
cur->next = cur->next->next;
pre = pre->next;
cur = cur->next;
}
pre->next = nullptr;
return res;
}
};面试题 02.07. 链表相交 - 力扣（LeetCode）
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。
图示两个链表在节点 c1 开始相交：
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
解题思路
双指针。首先我们要明确，当两指针相遇时，即为两个链表的交点。那么，何时相遇？同时迭代两链表，1° 当两链表前段长度相同时，显然会相遇。 2° 当两链表前端长度不等时，示意图如下：
等式表明：当两指针遍历完原链表后，再从另一链表表头开始迭代，会相遇。
代码实现
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB){
return nullptr;
}
ListNode *pa = headA, *pb = headB;
while(pa != pb){
pa = pa == nullptr ? headB:pa->next;
pb = pb == nullptr ? headA:pb->next;
}
return pa;
}
};