T3:(链表的必备熟练操作之一)翻转链表

给定单链表的头节点 head ，请反转链表，并返回反转后的链表的头节点。

解：

1.关键:

由于 翻转的 指针变化 ，需要逻辑清晰的 变化tmp ， head ，临时u这3个指针，次序很重要

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* reverseList(ListNode* head) {//这是一个基本的 操作，应该作为像“冒泡排序”一样熟练//tmp指向 head的 下一个节点，u作为临时节点//特殊情况if(head == NULL || head->next == NULL){return head;}//--ListNode* tmp=head->next;head->next=NULL;  //翻转后的 为节点的 next指针 置NULLwhile(tmp!=NULL && head!=NULL){//将tmp->next 给到u ，然后及那个tmp->next指向head,tmp给head，u给tmpListNode* u=tmp->next;tmp->next=head;head=tmp;tmp=u;}return head;}
};

T4: 判断一个链表是否为 “回文链表”

给定一个链表的 头节点 head ，请判断其是否为回文链表。

如果一个链表是回文，那么链表节点序列从前往后看和从后往前看是相同的。

解：

1.关键:

(1) 就是 3个 基本 操作的 组合: 快慢指针找到中间点 -- 翻转链表 -- 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:bool isPalindrome(ListNode* head) {//3个操作： 找中间点 - 翻转后半部分 - 2个链表的val比较//--特殊情况:if(head == NULL || head->next == NULL){return true;}//1.利用 快慢指针 找到中间点ListNode* fast=head->next;ListNode* slow=head;while(fast!=NULL && fast->next!=NULL){fast=fast->next->next;slow=slow->next;}ListNode* start=slow->next;slow->next= NULL;//2.翻转后半 链表ListNode *tmp = start->next;start->next=NULL; //翻转 后的 为节点的 next指针 置NULLwhile(tmp!=NULL && start!=NULL){ListNode* u=tmp->next;tmp->next=start;start=tmp;tmp=u;}//3. 2个链表之间的 比较 ,头节点分别 是 head 和 startwhile(head !=NULL && start!=NULL){if(head->val != start->val){return false;}head = head->next;start=start->next;}return true;}
};

T5:合并 多个 有序链表 

给定一个链表数组，每个链表都已经按升序排列。

请将所有链表合并到一个升序链表中，返回合并后的链表。

解：

1.关键：

（1）基础：2个有序链表的 排序

(2)思维： 利用 多元gcd的求解思维， 多元 == 依次二元

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* mergeKLists(vector& lists) {//这个题目 就是 多个 链表的 merge//借鉴 求解多元gcd的 思路，多个 == 依次 2个,所以只要不断调用 2个链表的 合并//特殊情况if(lists.size() == 0){return NULL;}ListNode* ans = lists[0];int size= lists.size();for(int i=1;ival < right->val){tmp->next=left;left=left->next;tmp=tmp->next;}else{tmp->next=right;right=right->next;tmp=tmp->next;}}//--那个还有剩余if(left!=NULL){tmp->next=left;}if(right!=NULL){tmp->next=right;}return ans->next;}};

T6:复杂链表的 复制

请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。

解：

1.关键：

（1）这是一道 关于  unordered_map 的问题

(2)首先 遍历 一次 ， 存储下 对应的 next指针 和 在map中存储 对应的Node的对应关系

(3)最后遍历一次， 存储对应的 random指针

2.代码:

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node* random;Node(int _val) {val = _val;next = NULL;random = NULL;}
};
*/
class Solution {
public:Node* copyRandomList(Node* head) {//特殊if(head == NULL){return NULL;}//设置一个 递增变量指针Node* tmp=head;//设置一个map用于存储对应的 Node的关系unordered_map Map;//利用一个map进行存储 两者对应的节点Node* new_head=new Node(head->val);Map[head]=new_head;tmp=tmp->next;Node* tmp2=new_head;while(tmp!=NULL){//每次开辟一个新的 NOde空间,Node* new_node=new Node(tmp->val);Map[tmp]=new_node;tmp2->next=new_node;tmp2=tmp2->next;tmp=tmp->next;//Map中存储对应的 Node的 关系:}//2.遍历了之后，需要 再次遍历 ，并且处理 random指针tmp=head;tmp2=new_head;while(tmp!=NULL){tmp2->random = Map[tmp->random];tmp=tmp->next;tmp2=tmp2->next;}return new_head;}
};

T7: 向 有序 环形链表中 insert一个节点

给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。

给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。

如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。

如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。

解：

1.关键:

(1) 模拟遍历查找 + insert节点操作（熟练）

(2)需要考虑 一些 特殊操作 和 取等、、、那些情况

2.代码：

/*
// Definition for a Node.
class Node {
public:int val;Node* next;Node() {}Node(int _val) {val = _val;next = NULL;}Node(int _val, Node* _next) {val = _val;next = _next;}
};
*/class Solution {
public:Node* insert(Node* head, int insertVal) {//思路： 直接模拟 遍历查找 + 插入一个节点的 操作即可//特殊情况:if(head == NULL){Node* new_head =new Node(insertVal);new_head->next = new_head;return new_head;}if(head->next == head){Node* new_head =new Node(insertVal);new_head->next = head;head->next = new_head;return head;}//（1）copy 保留开始 的head节点Node* tmp = head;Node* new_node=new Node(insertVal);//将这个new_node通过遍历 找到合适的 位置， 然后 执行insert操作//(2)遍历//符合条件的位置: tmp->val < next->val tmp->val < insertVal && tmp->next->val//或者: tmp->val > next->val  && tmp->val < insertVal int i=1;while(1){if(tmp == head && i!=1){//说明 所有的val都相同new_node->next = tmp->next;tmp->next = new_node;return head;}i++;cout<<"来过吗 "<val <val < tmp->next->val && tmp->next->val >= insertVal && tmp->val <= insertVal){new_node->next = tmp->next;tmp->next = new_node;return head;}else if(tmp->val > tmp->next->val && (tmp->val <= insertVal || tmp->next->val >= insertVal)){new_node->next = tmp->next;tmp->next = new_node;return head;}//case3:tmp=tmp->next;}//:只剩 一种case 需要考虑， 就是所有的 val都相等怎么办？//很简单 ， 那时候tmp一定会回到head,直接insert到这个位置即可}
};

T8:删除 链表 节点(基本操作)

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

解：

1.关键：

（1）利用 “双指针 ”找到需要删除的 节点的前驱节点

(2)然后 next 指next->next即可

2.代码：

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
class Solution {
public:ListNode* deleteNode(ListNode* head, int val) {//找到这个 节点的 前驱节点的指针即可ListNode* tmp=head->next;ListNode*tmp2=head;//特殊情况:if(head->val == val){head = head->next;return head;}//--一般情况:while(tmp->val !=val){tmp2=tmp;tmp = tmp->next;}tmp2->next = tmp2->next->next;return head;}
};