我家自动化

这个屌丝很懒，什么也没留下！

热门标签

数据结构：链表课程总结 + leetcode刷题_将n个数字插入空链表l中,使l形成递减有序链表

作者：我家自动化 | 2024-05-02 10:53:36

踩

将n个数字插入空链表l中,使l形成递减有序链表

Leetcode：

T1：利用 “归并排序” 对链表进行排序:

关键：

（1）merge_sort函数 : 递归函数--出口，直到只有1个或者 0个元素为止，直接返回这个节点，作用就是链表分成 2半，

(2)merge_sort函数中：因为是链表，所以需要利用 fast ，slow快慢指针找到中间位置，然后分别找到 left链表和 right链表的头节点（注意把 left链表的尾节点设置为 NULL）

(3)merge函数：不需要用递归实现，直接用while循环即可，直到其中有一个指针为NULL，最后接上剩下的那个链表（等价于上课讲到的 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* sortList(ListNode* head) {
        head=merge_sort(head);
        return head;
    }
    ListNode* merge_sort(ListNode* head)
    {
        //static int time=1;
 
        //cout<<"这是第"<<time++<<"次sort"<<endl;
        //出口 ，head长度为1 或 0 直接返回
        if(head == nullptr || head->next==nullptr)
        {
            return head;
        }
 
        //(1)利用 快慢指针 找到中间位置
        ListNode* fast=new ListNode(0);
        ListNode* slow=new ListNode(0);
        fast=head->next; //这种链表没有头节点，每个节点都有val
        slow=head;
        //fast 每次移动2格 ， slow移动一格
        while(fast!= NULL && fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        //(2)此时slow指向的位置就是向下取整的中间位置
        //递归，直到1个元素 或0 个元素
        ListNode* right=new ListNode(0);
        ListNode* left=new ListNode(0);
        right=merge_sort(slow->next); //右边链表的起点
        slow->next=NULL; //左边链表的尾部 置NULL
        left=merge_sort(head);
 
        head=merge(left,right);
        
        //尝试 添加一个新的 堆区空间
        ListNode* ans=new ListNode(0);
        ans=head;
        //show(ans);
        return ans; //head这个指针式传递进来的，可以返回，不是临时变量
    }
    //输出 函数
    void show(ListNode* node)
    {
        while(node!=NULL)
        {
            cout<<node->val<<endl;
            node=node->next;
        }
    }
 
    ListNode* merge(ListNode* left,ListNode* right)
    {
 
        //cout<<"left:"<<left->val<<"right:"<<right->val<<"merge一下"<<endl;
        //既然传递进来的 left 和 right都是 有序的 ，相当于 上课讲的链表merge合并
        ListNode* root_ =new ListNode(0);//堆区，防止销毁临时变量
        ListNode* root=new ListNode(0);
        root=root_;
        root->next=NULL;
        while(left!=NULL && right!=NULL)
        {
            if(left->val < right->val)
            {
                //left先进
                root->next= left;
                root=root->next;
                left=left->next;
            }
            else
            {
                //right进
                root->next=right;
                root=root->next;
                right=right->next;
            }
        }
        //(2)处理 剩余的 节点
        if(left!=NULL)
        {
            //左边非空
            root->next=left;
        }
        else if(right != NULL)
        {
            root->next= right;
        }
        return root_->next;
    }
};

T2: 重排链表（有点像 2个链表交错）

给定一个单链表 L 的头节点 head ，单链表 L 表示为：

L0 → L1 → … → Ln-1 → Ln
请将其重新排列后变为：

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

解：

1.关键：

（1）总的来说：就是3个操作：快慢指针找到中间点 -- 翻转后半链表 -- “交错合并”2个链表

(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:
    void reorderList(ListNode* head) {
        //妙啊，这种 “交错的结构”--找中间点 ， 然后对后半部分翻转 ,最后合并2个list
        //特殊，只有一个节点，直接返回
        if(head==NULL || head->next == NULL)
        {
            return ;
        }
        //1.找到中间点:(利用快慢指针 -- 找到“向下取整”的中间点)
        ListNode* fast=head->next;
        ListNode* slow=head;
        while(fast!=NULL && fast->next!=NULL)
        {
            fast=fast->next->next;
            slow=slow->next;
        }
        
        //此时slow就是那个“向下取整的”中间点
        //无所谓 ，反正 多出的哪一个 最后接上就好了
        //2.将slow->next 一直到 NULL前的 node进行翻转
        ListNode* start=slow->next;
        ListNode* tmp=start->next;  //tmp永远维持 start的原序的 下一个节点
        start->next=NULL; //翻转后的 “尾部” 置NULL
        //别忘记了，需要把 head的 最后一个节点的next置NULL
        slow->next=NULL;
        while(tmp!=NULL && start!=NULL)
        {
            //tmp需要 指向现在的 start然后tmp给start，把u给tmp
            ListNode* u=tmp->next;
            tmp->next=start;
            start=tmp;
            tmp=u;
            //成功翻转
        }
        //----测试： --好了， 上面的 步骤都没问题
        //show(head);
        //show(start);
 
        //tmp==NULL,start指向新的起点
        //3.好了2个链表的起点分别是head 和 start
        //开始 “交错合并”2个链表
        ListNode* pa=head;
        ListNode* pb=start;
        ListNode* pc=new ListNode(0);//头节点
        ListNode* new_head=pc;
        while(pa!=NULL && pb!=NULL)
        {
            pc->next=pa;
            pa=pa->next;
            //--次序
            pc=pc->next;
            pc->next=pb;
            pb=pb->next;
            pc=pc->next;
        }
        if(pa!=NULL)
        {
            pc->next = pa;
        }
        if(pb!=NULL)
        {
            pc->next=pb;
        }
        head=new_head->next;
 
    }
    //测试函数
    void show(ListNode* node)
    {
        while(node!=NULL)
        {
            cout<<node->val<<" ";
            node=node->next;
        }
        cout<<endl;
    }
};

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指针 置NULL
        while(tmp!=NULL && head!=NULL)
        {
            //将tmp->next 给到u ，然后及那个tmp->next指向head,tmp给head，u给tmp
            ListNode* 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指针 置NULL
        while(tmp!=NULL && start!=NULL)
        {
            ListNode* u=tmp->next;
            tmp->next=start;
            start=tmp;
            tmp=u;
        }
        //3. 2个链表之间的 比较 ,头节点分别 是 head 和 start
        while(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<ListNode*>& lists) {
        //这个题目 就是 多个 链表的 merge
        //借鉴 求解多元gcd的 思路，多个 == 依次 2个,所以只要不断调用 2个链表的 合并
        //特殊情况
        if(lists.size() == 0)
        {
            return NULL;
        }
        ListNode* ans = lists[0];
        int size= lists.size();
        for(int i=1;i<size;i++)
        {
            ans=merge(ans,lists[i]);
        }
        return ans;
    }
    //2个 有序链表的 合并函数
    ListNode* merge(ListNode* left, ListNode* right)
    {
        ListNode* tmp=new ListNode(0);
        ListNode* ans=tmp;
        while(left!=NULL && right!=NULL)
        {
            //case1 : left小:
            if(left->val < 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<Node*,Node*> 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<<"来过吗 "<<tmp->val <<endl;  //--陷入死循环
            if(tmp->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;
 
    }
};

T9:展平多级双向链表

多级双向链表中，除了指向下一个节点和前一个节点指针之外，它还有一个子链表指针，可能指向单独的双向链表。这些子列表也可能会有一个或多个自己的子项，依此类推，生成多级数据结构，如下面的示例所示。

给定位于列表第一级的头节点，请扁平化列表，即将这样的多级双向链表展平成普通的双向链表，使所有结点出现在单级双链表中。

解：

1.关键：

（1）这个 “结构图 ”一看马上反应过来就是 dfs(深搜) ，然后直接用递归实现

(2)重点是，处理好每次dfs的出口时 head->next == NULL 以及最后一个节点的 child是否还有，

！！每次返回的都是 “当前这一层的最后一个节点的指针” , 除非是 next为 NULL，而child不为NULL，这时候就需要返回下一层的最后一个节点，作为 “这一层的”最后一个节点

2.代码：


/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* prev;
    Node* next;
    Node* child;
};
*/
 
class Solution {
public:
    Node* flatten(Node* head) {
        //很明显的 一个 dfs深度优先搜索的 结构
        //特殊:
        if(head == NULL)
        {
            return NULL;
        }
        dfs(head);
        //--遍历一次， 置空所有的 CHILD指针域
        Node* tmp=head;
        while(tmp!=NULL)
        {
            tmp->child = NULL;
            tmp= tmp->next;
        }
        return head;
    }
    Node* dfs(Node* head)
    {
        //这个递归 函数的 出口就是 next =NULL ,返回 每一层的 最后一个NOde的指针
        Node* pa = new Node;
        pa = head; //和head指向同一个 对象
        //1.出口
        if(head->next == NULL)
        {
            if(head->child != NULL)
            {
                
                head->next = head->child;
                head->child->prev = head;
                head=dfs(head->child);  //先深搜一次(下一层的连接)然后再 进行连接
                return head;
            }
            else{
                return head;
            }
        }
        //2.递归:
        
        //--递归 搜索
        while(pa->next !=NULL)
        {
            if(pa->child != NULL)
            {
                //需要 再深入 一层递归 ， 并且返回 递归结果的头节点指针
                //(1)存下 这一层的 next 的指针
                Node* next_=pa->next;
                //(2)让pa的next 和 pre 和 child进行 互相交织
                pa->next = pa->child;
                pa->child->prev = pa;
                //(3)返回递归 得到的 下一层的最后一个 node的 指针
                //然后和 next_进行交织
                Node* tmp=dfs(pa->child); //返回 下一层的 最后一个节点的指针
                tmp->next = next_;
                next_->prev = tmp;
                //--更新pa 到next_
                pa = next_;
            }
            else
            {
                pa= pa->next; //直接更新 pa
            }
            //pa指向 下一个位置
        }
        //有一种可能， pa->next == NULlL ,倒是child还有
        if(pa->child != NULL)
        {
            
            pa->next = pa->child;
            pa->child->prev = pa;
            pa=dfs(pa->child);  //先深搜一次(下一层的连接)然后再 进行连接
        }
        return pa; //此时pa就是这一层的 最后一个节点
    }
    //最后一步 ， 就是 将所有的child 域全部置空
 
};

T10：判断链表是否相交

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。

图示两个链表在节点 c1 开始相交：

解：

1.关键：

（1）利用 set 容器存储第一条链表中的所有节点

(2)第二次遍历一次第二条链表判断是否 count 重复出现的节点，如果有就直接返回了

2.代码:


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        //利用set容器存储 第一条链表的 所有节点，然后遍历一次第二条链表即可
        unordered_set<ListNode*> Set;
        //(1)遍历第一条 链表
        ListNode* node1=headA;
        while(node1!=NULL)
        {
            Set.insert(node1);
            node1=node1->next;
        }
        //(2)遍历第二条 链表 + 判断是否在set中出现过
        node1 = headB;
        while(node1!=NULL)
        {
            if(Set.count(node1))
            {
                return node1;
            }
            node1=node1->next;
        }
        return NULL;
    }
};

T11:又是对一个链表进行排序（熟练掌握归并排序）

给你链表的头结点 head ，请将其按升序排列并返回 排序后的链表 。

解：

1.关键：

（1）归并排序 = 递归函数merge_sort + 2个有序链表的“合并”的merge函数

(2)merge_sort函数:递归

<1>出口if(head == NULL || head->next==NULL) （0个或 1个节点，就是有序的，直接返回）

<2>将传递进来的1个链表head 拆分为大小几乎相同的两个链表，利用快慢指针找到“中间点”（记得将 left链表的最后一个节点的 next指针置空）

<3>然后 left = merge_sort(head) ,right = merge_sort(start) ,分别递归，返回的时候都是 2个有序链表的头节点

<4>最后 merge（left,right）, 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* sortList(ListNode* head) {
        //利用 归并 排序 ，对一条链表进行 排序
        return merge_sort(head);
    }
 
    ListNode* merge_sort(ListNode* head)
    {
        //特殊
        if(head==NULL || head->next == NULL)
        {
            return head;
        }
        //不断的 分治 ， 先递归 进入到 最深的 只有一个元素的有序情况,然后调用merge
        //(1)找到 当前 这一层的 中间点
        //利用 快慢指针实现
        ListNode* fast= head->next;
        ListNode* slow= head;
        while(fast!=NULL && fast->next!=NULL)
        {
            fast= fast->next->next; 
            slow = slow->next;
        }
        //此时slow已经指向 “向下取整的中间点”
        //(2)分成2个链表进行递归
        ListNode* start=slow->next;
        slow->next= NULL;
        //head 和 start
        ListNode* left = merge_sort(head);
        ListNode* right = merge_sort(start);
        //--返回的 都是 已经排序完成的  头节点
        return merge(left,right);
    }
 
    ListNode* merge(ListNode* pa,ListNode* pb)
    {
        //特殊
        if(pa == NULL)
        {
            return pb;
        }
        if(pb == NULL)
        {
            return pa;
        }
        //(1)这个函数 ，传递进来2个 头节点的 指针，都是有序的 ，相当于是合并2个有序
        //自己设计一个 头节点，然后 返回头节点 next指针即可
        ListNode* pc=new ListNode(0);
        ListNode* tmp=pc;
        while(pa!=NULL && pb!=NULL)
        {
            //case1:
            if(pa->val < pb->val)
            {
                pc->next = pa;
                pa=pa->next;
                pc=pc->next;
            }
            else
            {
                pc->next = pb;
                pb= pb->next;
                pc=pc->next;
            }
        }
        //--收尾
        if(pa!=NULL)
        {
            pc->next = pa;
        }
        if(pb!=NULL)
        {
            pc->next = pb;
        }
        return tmp->next;
 
    }
};

T12:用链表表示的 2个整数的求和

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

解：

1.关键:

（1）思路一：先求出总和，然后造一个链表（利用除10 mod10的思路）

（2）思路二：借助全加器的思想，利用串行进位的 while循环方法， a,b,c得到本位和然后同时进行链表的构造，不断更新进位，别忘了最后一个进位c不为0的时候，需要创造一个节点

2.代码：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //第二种方法： 相当于是 写一个 全加器, 然后 循环 串行相加
        //特殊情况：
        if(l1 == NULL)
        {
            return l2;
        }
        if(l2 == NULL)
        {
            return l1;
        }
        //--
        ListNode* l3=new ListNode(0);
        ListNode* head = l3;
        int a=l1->val,b=l2->val,c=0,sum=0;
        while(l1!=NULL && l2!=NULL)
        {
            a=l1->val;
            b=l2->val;
 
            sum=(a+b+c)%10;  //本位和
            //--造链表
            ListNode* node= new ListNode(sum);
            l3->next = node;
            l3=l3->next;
 
            c=(a+b+c)/10;   //进位和
 
            l1=l1->next;
            l2=l2->next;
 
        }
        //收尾：
        while(l1 != NULL)
        {
            sum=( c+ l1->val)%10;
            c=(c+l1->val)/10;
            //--造链表
            ListNode* node= new ListNode(sum);
            l3->next = node;
            l3=l3->next;
 
            c=(c+l1->val)/10;
            l1=l1->next;
        }
        //--
        while(l2!=NULL)
        {
            sum=(c+l2->val)%10;
            c=(c+l2->val)/10;
            ListNode* node= new ListNode(sum);
            l3->next = node;
            l3=l3->next;
 
            c=(c+l2->val)/10;
            l2=l2->next;
        }
        //如果 最终的 c的值不为0 ，还需要 造一个节点
        if(c!= 0 )
        {
            ListNode* node= new ListNode(c);
            l3->next = node;
            l3=l3->next;
        }
        return head->next;
    }
};

T13：分隔链表(以数值x为界限)

给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有小于 x 的节点都出现在 大于或等于 x 的节点之前。

你应当保留两个分区中每个节点的初始相对位置。

解:

1.关键：

（1）利用 2个标记位置不动的节点head1，head2 ，以及不断移动的 2个节点p1，p2

(2)遍历一次 “原链表” ，然后在“对应的位置” 执行 “节点插入的基本操作”

（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* partition(ListNode* head, int x) {
        //特殊情况:
        if(head == NULL || head->next== NULL)
        {
            return head;
        }
        //采用 不断插入的 思想，2个 相对插入位置
        ListNode* p1=new ListNode(0);
        ListNode* p2=new ListNode(0);
        ListNode* head1 = p1;
        ListNode* head2 = p2; //head不动， p指针不断移动
        //(1)初始链表
        p1->next=p2;
        //(2)while循环插入
        //val < x则 插入到p1 和 head2之间，并且更新p1
        //否则 ，连接接到p2之后，并且 更新p2
        while(head!=NULL)
        {
            //保留head->next
            ListNode* tmp = head->next;
            if(head->val < x)
            {
                head->next = p1->next;
                p1->next = head;
                p1 = p1->next;
            }
            else
            {
                p2->next = head;
                p2= p2->next;
            }
            head=tmp;
        }
        p2->next=NULL;
 
        //（3）删除 标志节点:head2 需要删除
        p1->next = p1->next->next;
        return head1->next;
 
 
    }
};

T14：分割链表，将一个链表分割为 k个部分

给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。

每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。

这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。

返回一个由上述 k 部分组成的数组。

解：

1.关键：

（1）遍历一次，得到链表的总长度

(2)特殊情况 ,k > n时需要返回一个长度为 k 的vector

(3)一般情况，大概是一个数论题目： cnt2 = n/k--表示后面的子链表长度，cnt1长度的子链表一共有 n%k =diff 个，然后遍历一次对链表进行切割即可

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:
    vector<ListNode*> splitListToParts(ListNode* head, int k) {
        //就是将 一个 链表 分割为k个 链表 ，重点在于 计算链表的长度，和数论有关
        vector<ListNode*> vec;
        //(1)遍历一次 ，得到总长度n
        ListNode* tmp=head;
        int n=0;
        while(tmp !=NULL)
        {
            n++;
            tmp = tmp->next;
        }
        //特殊 ： k > n
        //需要 将 原链表全部割开
        if(k > n)
        {
            vector<ListNode*> ans(k);  //大小为k
            int i=0;
            while(head !=NULL)
            {
                ListNode* u= head->next;
                head->next = NULL;
                ans[i++] = head;
                head = u;
            }
            return ans;
        }
        
 
        //(2)计算 各个数值
        int cnt2= n/k;
        int diff=n%k;
        //需要有 diff 个前面的 链表长度为cnt2+1
        int cnt1= cnt2+1;
        //(3)再次遍历:
        int i=1;
        for(i=1 ; i <= diff ;i++)
        {
            ListNode* new_head=head;
            //直接原地 分割好了
            for(int j=1;j<=cnt1-1;j++)
            {
                head = head->next;
            }
            ListNode* next_head = head->next;
            head->next= NULL;
            vec.push_back(new_head);
            head = next_head;
            //此时 head指向的是 长度为cnt1的 子链表的最后一个节点
        }
        //--继续
        for(i=diff+1 ; i <= k ;i++)
        {
            cout<<"第二部分 来过几次 "<<endl; //只来过一次？ why
            ListNode* new_head=head;
            //直接原地 分割好了
            for(int j=1;j<=cnt2-1;j++)
            {
                head = head->next;
            }
            ListNode* next_head = NULL;
            if(head != NULL)
            {
                next_head = head->next;
            }
            else
            {
                continue;
            }
            head->next= NULL;
            vec.push_back(new_head);
            head = next_head;
            //此时 head指向的是 长度为cnt1的 子链表的最后一个节点
        }
        return vec;
        //还要 考虑 k > n的情况
        
    }
};

T15：从尾到头打印链表中的元素

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解：

1.关键：

（1）等价于 stack栈结构中的 “后进先出”

(2)不需要反转链表，只要通过遍历一次得到链表的总长度，然后反向存储数值即可

2.代码：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        //先遍历一次 获取长度n,（不需要反转），然后 从vec的后面开始存放数值
        //其实利用一个stack更好， 后进先出
        int n=0;
        ListNode* tmp= head;
        while(tmp!= NULL)
        {
            n++;
            tmp=tmp->next;
        }
        vector<int> ans(n);
        while(head != NULL)
        {
            ans[--n] = head->val;
            head = head->next;
        }
        return ans;
    }
};

T16:链表表示的 2个整数相加(高位在前 version)

给定两个 非空链表 l1和 l2 来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

可以假设除了数字 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //这一次 是 高位在 链表的 前面，低位在 链表的 后面
        //特殊情况：
        if(l1 == NULL)
        {
            return l2;
        }
        if(l2 == NULL)
        {
            return l1;
        }
        //思路一：可以考虑 反转链表之后 按照原来的 方法进行求解
        //因为 从高位 到 低位的 串行进位 全加器是 做不到的 ,所以 还是 反转吧
        l1=reverse_list(l1);
        l2=reverse_list(l2);
        //--按照反转之后的计算（串行进位 全加器）
        int a=0,b=0,c=0,sum=0;
        ListNode* head=new ListNode(0);
        ListNode* l3=head;
        while(l1!=NULL && l2!=NULL)
        {
            a=l1->val;
            b=l2->val;
            sum=a+b+c;
 
            c=sum/10;
            ListNode* node=new ListNode(sum%10);
            l3->next = node;
            l3=l3->next;
 
            l1=l1->next;
            l2=l2->next;
 
        }
        //收尾
        while(l1 !=NULL)
        {
            sum = l1->val +c;
            c=sum/10;
 
            ListNode* node=new ListNode(sum%10);
            l3->next = node;
            l3=l3->next;
 
            l1=l1->next;
        }
        while(l2 !=NULL)
        {
            sum = l2->val +c;
            c=sum/10;
 
            ListNode* node=new ListNode(sum%10);
            l3->next = node;
            l3=l3->next;
 
            l2=l2->next;
        }
        //--
        if(c!=0)
        {
            ListNode* node=new ListNode(c);
            l3->next = node;
            l3=l3->next;
        }
        head = reverse_list(head->next);
        return head;
        
    }
    //反转链表函数
    ListNode* reverse_list(ListNode* list)
    {
        //特殊 情况:
        if(list == NULL || list->next == NULL)
        {
            return list;
        }
        //--一般情况:
        ListNode* tmp=list->next;
        list->next =NULL;
        while(tmp!=NULL)
        {
            ListNode* u= tmp->next;
            tmp->next = list;
            list = tmp;
            tmp = u;
        }
        return list;
        //悟：按 “值返回一个指针” 等价于“返回这个 指针的指向(本质上一个地址而已)”
    }
};

T17:判断链表中环的入口节点

给定一个链表，返回链表开始入环的第一个节点。从链表的头节点开始沿着 next 指针进入环的第一个节点为环的入口节点。如果链表无环，则返回 null。

为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。

说明：不允许修改给定的链表。

解：

1.关键：

（1）这和那个判断“2个链表相交节点很像”，都是利用Set 存储第一次 “经过！”该节点，然后利用Set判断是否有第一次重复经过

2.代码：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        //直接 利用 set进行判断 发生重复的 第一个节点就是入环的 节点
        unordered_set<ListNode*> Set;
        ListNode* tmp = head;
        //(1)遍历一次
        while(tmp!=NULL)
        {
            if(Set.count(tmp))
            {
                return tmp;
            }
            else
            {
                Set.insert(tmp);
            }
            tmp = tmp->next;
        }
        return NULL; //出来了，说明没有环
    }
};

T18:链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。

实现 Solution 类：

Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等
解

解：

1.关键：

（1）由于链表结构不利于随机访问，所以使用一个数组进行存储

(2)利用rand()%size 进行随机读取

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:
    //借助一个 数据数组进行存储
    vector<int> vec;
    int size;
    Solution(ListNode* head) {
        //利用一个 链表中的数据 进行初始化 数据数组
        //随机访问 直接返回 数组中的元素即可
        while(head != NULL)
        {
            vec.push_back(head->val);
            head = head->next;
        }
        size = vec.size();
    }
    
    int getRandom() {
        //随机
        //srand((unsigned)time(NULL));  //种下随机数种子
        int index = rand()%size;
        return vec[rand()%size];
 
    }
};
 
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(head);
 * int param_1 = obj->getRandom();
 */

T19:返回链表中倒数第k个节点

输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。

例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。

解：

1.关键：

（1）利用快慢指针让2个指针之间的距离是k-1个节点

（2）当fast到达最后一个节点时， slow就是倒数第k个节点

2.代码：


/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* getKthFromEnd(ListNode* head, int k) {
        //特殊：
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        //利用快慢指针 返回 单数第k个节点
        ListNode* fast=head;
        ListNode* slow=head;
        for(int i=1;i<=k-1;i++)
        {
            fast=fast->next;
        }
        while(fast->next!=NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        return slow;
    }
};

T20:中序遍历二叉搜索树构建双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。

解：

1.关键：（这个思路是我经历了很多失败后，无奈的选择，虽然比较笨，但还是比较通用）

（1）利用递归写一个中序遍历的代码

（2）将 “访问该节点” 改为 “将该节点加入到vec中”

(3)最后对 vec进行连接即可

2.代码：


class Solution {
public:
    vector<Node*> vec;
    Node* treeToDoublyList(Node* root) {
        //特殊：
        if(root == NULL)
        {
            return root;
        }
        if(root->left ==NULL && root->right == NULL)
        {
            root->left =root;
            root->right =root;
            return root;
        }
        //干脆用一个全局vec进行存储,tmd
        travel(root);
        int size=vec.size();
        //(遍历进行连接
        vec[0]->left = vec[size-1];
        vec[0]->right =vec[1];
        vec[size-1]->right = vec[0];
        vec[size-1]->left =vec[size-2];
        //
        for(int i=1;i<=size-2;i++)
        {
            vec[i]->left = vec[i-1];
            vec[i]->right = vec[i+1];
        }
        return vec[0];
        
    }
    //利用 递归 来写 中序遍历
    void travel(Node* root) //需要 返回 遍历之后的最后一个节点
    {
        //（1）递归出口
        if(root ==NULL)
        {
            return ;
        }
        
        //(2)递归
        travel(root->left);
        //此时的root就是 你想要的 次序
        vec.push_back(root);
 
        travel(root->right);
    }
};

T21：二进制链表转为一个十进制整数

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

解：

1.关键：

（1）一般，都是按照从低位到高位的次序进行处理的

(2)如果链表先存储高位，可以反转，或者改用一个vector进行存储，最后反向取出即可

(3)权值： power*=2 进行更新

2.代码:


class Solution {
public:
    int getDecimalValue(ListNode* head) {
        //(1)可以反转 、 也可以先用一个vec存储
        vector<int> vec;
        while(head!=NULL)
        {
            vec.push_back(head->val);
            head= head->next;
        }
        //(2)权值和
        long long power=1;
        long long sum=0;
        int size = vec.size();
        for(int i=size-1;i >=0 ;i--)
        {
            sum+= (vec[i] * power);
            power *=2;
        }
        return sum;
    }
};

T22: 一颗二叉树的每一层节点构成一个链表返回它们组成的 vector

给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组

解：

1.关键：

（1）二叉树的层序遍历：果断 bfs广搜，

(2)这里需要 2层交替，所以创新使用2个队列queue 交替存储下一层树节点的同时，将这一层的所有节点全部取出链接为一个新的链表

(3)bfs函数中：主要负责判断2个队列是否都为空的结束情况，并将每次搜索的返回的链表入vec

(4)update函数中：主要负责从其中一个不为空的队列中取出所有节点构建一条链表，同时向2个方向搜索的节点一次加入到另一个队列中

2.代码：


/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<ListNode*> listOfDepth(TreeNode* tree) {
        //采用 一种 不一样的 bfs广搜的 方式，每次都将 queue队列中的 元素全部取出
        return bfs(tree);
    }
 
    vector<ListNode*> bfs(TreeNode* root)
    {
        //考虑使用 2个队列交替 运作的 方式,每次都 只搜索一层
        queue<TreeNode*> Que1;  //不需要map因为 不会重复
        queue<TreeNode*> Que2;
        Que1.push(root);  //第一层 再Que1中
        vector<ListNode*> ans;
        while((!Que1.empty()) || (!Que2.empty()))
        {
            //只有当 2 个队列都为空的 时候 才需要退出
            ans.push_back(update(Que1,Que2));
        }
        return ans;
 
    }
 
    ListNode* update(queue<TreeNode*>& Que1,queue<TreeNode*>& Que2)  //2个搜索方向 
    {
        //传进来的队列 一个为空， 另一个个不为空
        //忘记 新的元素加入队列了
        //case1:Que2为空
        if(!Que1.empty())
        {
            //好了，这个 队列中的元素 一次作为一条新链表的 元素
            //ListNode* head=new ListNode(Que1.front()->val);
            TreeNode* head =Que1.front();
            ListNode* head_=new ListNode(head->val);
            //两个节点不是同一种
            
            Que1.pop();
            ListNode* tmp=new ListNode(0);
            ListNode* real_head = head_;
            while(head_!=NULL)
            {
                //--先元素新的 子节点入队
            if(head->left!=NULL)
            {
                Que2.push(head->left);
            }
            if(head->right != NULL)
            {
                Que2.push(head->right);
            }
                tmp->next = head_;
                tmp = tmp->next;
                if(Que1.empty())
                {
                    break;
                }
                head = Que1.front();
                head_ = new ListNode(head->val);
                Que1.pop();
            }
            return real_head;
        }
        else
        {
            TreeNode* head=Que2.front();
            ListNode* head_=new ListNode(head->val);
            Que2.pop();
            ListNode* tmp=new ListNode(0);
            ListNode* real_head = head_;
            while(head_!=NULL)
            {
            if(head->left!=NULL)
            {
                Que1.push(head->left);
            }
            if(head->right != NULL)
            {
                Que1.push(head->right);
            }
                tmp->next = head_;
                tmp = tmp->next;
                if(Que2.empty())
                {
                    break;
                }
                head = Que2.front();
                head_ = new ListNode(head->val);
                Que2.pop();
            }
            return real_head;
        }
    }
};

T23:反转部分链表

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

解：

1.关键：

(0)先考虑好那些特殊情况，比如left == right，无需反转

（1）找到left节点的前一个位置的节点作为head1,right的那个节点作为head2

(2)然后利用 “基本操作”对 head1->next 到 head2之间的节点进行反转，并且和head1 和 head2->next进行连接

(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* reverseBetween(ListNode* head, int left, int right) {
        //反转第left 到 right之间的 节点
        //特殊情况： 如果left==1
        if(head == NULL || head->next==NULL || left==right)
        {
            return head;
        }
        //（1）先获取到 left的前一个节点 和 right节点
        ListNode* head1 = new ListNode(0);
        ListNode* head2 = new ListNode(0);
        ListNode* start = head;
        int k=1;
        for(k=1; k <= left-2 ; k++)
        {
            start = start->next;  
        }//现在start指向的 就是 left前一个节点
        if(left == 1)
        {
            start = head1;
            head1->next = head;
        }
        head1 =start;  //将这个节点给到head1
        //cout<<"左节点"<<head1->val<<endl; //有问题，需要left前一个节点
        int diff = right - left;
        for(k=1;k<=diff+1 ; k++)
        {
            start = start->next;
        }
        head2 = start;  //现在head2就是 指向right节点
        //cout<<"右节点"<<head2->val<<endl; 
        //(2)然后开始 反转
        start = head1->next;
        ListNode* tmp = start->next;
        start->next = head2->next;  //连上右侧
        head2->next = NULL;
        while(tmp!=NULL && start!=NULL)
        {
            ListNode* u =tmp->next;
            tmp->next = start;
            start= tmp;
            tmp= u;
        }
        //此时start指向尾节点
        head1->next = start;
 
        if(left != 1)
        {
            return head;
        }
        else
        {
            return start;
        }
        
    }
};

T24:先删除部分链表，然后在对应位置连接一个新的链表

给你两个链表 list1 和 list2 ，它们包含的元素分别为 n 个和 m 个。

请你将 list1 中下标从 a 到 b 的全部节点都删除，并将list2 接在被删除节点的位置。

解：

1.关键：

（1）坑：这个题中下标从0开始计数

(2)其实和T23一样，重点是得到 left的前一个节点 head1 , 和 right的那个节点 head2

（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* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        //删除节点 + 插入节点
        //(1)先找到a前面的 那个节点 和 b的那个节点
        ListNode* head=new ListNode(0);
        head->next = list1;
        ListNode* tmp=head;
        ListNode* head1= tmp;
        a+=1;
        b+=1;
        for(int k=1; k<= a-1; k++)
        {
            tmp = tmp->next;
        }
        head1 = tmp ;//a前面的节点
        cout<<"left: "<<head1->val<<endl; //left找错了
        //tmd 的 下标从0开始用
        int diff = b-a;
        for(int k=1;k<= diff+1;k++)
        {
            tmp = tmp->next;
        }
        ListNode* head2= tmp; //b的那个节点
        cout<<"right: "<<head2->val<<endl;
        //(2)开始删除
        head1->next = list2;
        while(list2->next !=NULL)
        {
            list2 = list2->next; //找到list2的最后一个节点
        }
        list2->next = head2->next;
        //
        return head->next;
    }
};

T25:删除利用val区分不同节点的链表中的给定节点

有一个单链表的 head，我们想删除它其中的一个节点 node。

给你一个需要删除的节点 node 。你将 无法访问 第一个节点 head。

链表的所有值都是 唯一的，并且保证给定的节点 node 不是链表中的最后一个节点。

删除给定的节点。注意，删除节点并不是指从内存中删除它。这里的意思是：

给定节点的值不应该存在于链表中。
链表中的节点数应该减少 1。
node 前面的所有值顺序相同。
node 后面的所有值顺序相同。
解：

解：

1.关键：

（1）利用不同 val进行区分，暗示可以修改节点的val值

(2)一句话：“先把自己变成儿子，然后干掉儿子”

2.代码：


class Solution {
public:
    void deleteNode(ListNode* node) {
        //妙啊：这题 可以改变节点的 数值，因为每个节点的数值都不同，所以利用val区分
        //一句话：“先把自己变成儿子，然后干掉儿子”
        //之所以不是 末尾节点，就是保证有儿子
        node->val = node->next->val;
        node->next=node->next->next;
    }
};

T26:删除链表的 “中间点”

给你一个链表的头节点 head 。删除链表的 中间节点 ，并返回修改后的链表的头节点 head 。

长度为 n 链表的中间节点是从头数起第 ⌊n / 2⌋ 个节点（下标从 0 开始），其中 ⌊x⌋ 表示小于或等于 x 的最大整数。

对于 n = 1、2、3、4 和 5 的情况，中间节点的下标分别是 0、1、1、2 和 2 。

解：

1.关键：

（1）这里的中间点的 “下标”是从0开始计算的，但是 n又是从1开始算的

(2)如果fast的终止条件是 fast!=NULL && fast->next!=NULL 那么

奇数个点： slow指向的正好是“真中间点” 偶数个点： slow指向 “向下取整”的中间点

(3)所以终止条件改为 fast!=NULL && fast->next!=NULL && fast->next->next!=NULL

得到的slow才是前一个节点（偶数点时）

2.代码：


class Solution {
public:
    ListNode* deleteMiddle(ListNode* head) {
        //利用 快慢指针 找到“向下取整的 ”中间节点 或者是 “真中间点”
        //特殊
        if(head == NULL || head->next == NULL)
        {
            return NULL;
        }
        //--
        ListNode* fast = head->next;
        ListNode* slow =head;
        while(fast!=NULL && fast->next!=NULL && fast->next->next!=NULL)
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        slow->next = slow->next->next;
        return head;
    }
};

T27:最大孪生和

在一个大小为 n 且 n 为偶数的链表中，对于 0 <= i <= (n / 2) - 1 的 i ，第 i 个节点（下标从 0 开始）的孪生节点为第 (n-1-i) 个节点。

比方说，n = 4 那么节点 0 是节点 3 的孪生节点，节点 1 是节点 2 的孪生节点。这是长度为 n = 4 的链表中所有的孪生节点。

孪生和 定义为一个节点和它孪生节点两者值之和。

给你一个长度为偶数的链表的头节点 head ，请你返回链表的 最大孪生和 。

解：

1.关键：

（1）其实主要考察反转或者改用 vector 存储利于随机访问

2.代码:


class Solution {
public:
    int pairSum(ListNode* head) {
        //最大孪生和 ， 可以反转 ，也可以 先存到vec中
        vector<int> vec;
        while(head!=NULL)
        {
            vec.push_back(head->val);
            head = head->next;
        }
        int size= vec.size();
        //--打擂台
        int half = size/2;
        int max=-1;
        for(int i=0;i<=half-1;i++)
        {
            int sum = vec[i] + vec[size-1-i];
            if(sum > max)
            {
                max = sum;
            }
        }
        return max;
    }
};

T28:给一个从高位开始表示的链表整数 +1

给定一个用链表表示的非负整数，然后将这个整数 再加上 1 。

这些数字的存储是这样的：最高位有效的数字位于链表的首位 head 。

解：

1.关键：

（1）等价于只有个位的一个进位c=1

（2）然而，无论如何都只能从低位开始向高位串行进位

（3）所以，翻转+串行进位+翻转

2.代码：


class Solution {
public:
    ListNode* plusOne(ListNode* head) {
        //和2个链表 表示的 整数的 求和思路一样 ， 都是串行进位求和
        //(1)翻转
        head = reverse(head);
        //show(head);
        ListNode* new_head =head;
        //(2)串行进位求和
        int c=1;
        ListNode* before_head=head;
        while(head!=NULL)
        {
            int sum = c + head->val;
            c=sum/10;
            head->val = sum%10;
            before_head = head;
            head = head->next;
        }
        //收尾 -- 很可惜 ，这是的head是一个NULL指针
        if(c!=0)
        {
            ListNode* node = new ListNode(c);
            before_head->next = node;
        }
        head = reverse(new_head);
        return head;
 
    }
    //翻转函数
    ListNode* reverse(ListNode* head)
    {
        ListNode* start = head;  //start指向翻转后的 头节点
        if(head!=NULL && head->next != NULL)
        {
            ListNode* tmp =start->next;
            start->next =NULL;
            while(tmp!=NULL && start!=NULL)
            {
                ListNode* u = tmp->next;
                tmp->next = start;
                start= tmp;
                tmp= u;
            }
        }
        return start;
    }
    //测试 函数
    void show(ListNode* head)
    {
        ListNode* tmp = head;
        while(tmp!=NULL)
        {
            cout<<tmp->val <<" ";
            tmp = tmp->next;
        }
        cout<<endl;
    }
};

T29:交换单链表中正数第k个节点和倒数第k个节点

给你链表的头节点 head 和一个整数 k 。

交换链表正数第 k 个节点和倒数第 k 个节点的值后，返回链表的头节点（链表 从 1 开始索引）。

解：

1.关键：

（1）从head移动k-1次得到正数第k个节点

（2）利用相隔k个节点的 fast slow快慢指针找到倒数第k个节点，当fast==NULL时终止

(3)值交换即可

2.代码：


class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        //交换 链表 正数 和 倒数的 第k个 节点的！值！，好吧，“值交换”
        //还不如 分别 取到 第k个节点 和 快慢指针得到的 倒数 第k个节点
        ListNode* node1 = head;
        for(int i=1;i<=k-1;i++)
        {
            node1 = node1->next;
        }//此时 node1指向的 就是 正数 第k个节点
        //(2)
        ListNode* fast =head;
        ListNode* slow =head; //fast==NULL时，如果2者相隔k个节点
        for(int i=1;i<=k;i++)
        {
            fast = fast->next;
        }
        while(fast!=NULL)
        {
            fast = fast->next;
            slow = slow->next;
        }
        //交换
        swap(slow->val , node1->val);
        return head;
    }
   
};

T30:限定insert排序，对链表进行 insert排序

给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。

插入排序 算法的步骤:

插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
重复直到所有输入数据插入完为止。

下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。

对链表进行插入排序。

解：

1.关键：

（1）设置一个 tail节点每次都指向已经排序好的最后一个节点

(2)设置一个 u节点，指向下一个需要排序的节点

(3)内层循环判断 node1 的val是否在 xx和xx之间，或者放到末尾并且更新tail指针

2.代码：


class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        //训练 插入排序的熟练程度
        //特殊：
        if(head == NULL || head->next ==NULL)
        {
            return head;
        }
        //我需要 一个 tail 节点  -- 已经排序完成的 最后一个节点
        //只有当 node1 放到 tail的后面时 才需要 更新tail
        ListNode* tail =head;
        //--一般:
        ListNode* node1 = head->next;
        while(node1 !=NULL)
        {
            //特殊:
            ListNode* u = node1->next;  //作为 最后 node1的更新节点
            tail->next = u ;//将u连接到 tail后面
            if(node1->val < head->val)
            {
                node1->next = head;
                head = node1;
                node1 = u;
                continue;
            }
            ListNode* tmp = head;
            //内层循环
            int flag = 0;
            while(tmp!= tail) //终点为 tail节点
            {
                if( node1->val >= tmp->val && node1->val <=tmp->next->val)
                {
                    //可以放到它两之间了
                    node1->next = tmp->next;
                    tmp->next = node1;
                    node1 = u;
                    flag =1;
                    break;
                }
                else
                {
                    tmp = tmp->next;
                }
            }
            if(flag == 1)
            {
                continue;
            }
            else{
                //需要更新tial节点,此时 tmp指向 tail
                tmp->next = node1;
                tail = node1;
                node1 = u;
            }
 
            node1 = u;
            
        }
        return head;
    }
};

T31: 逆序打印节点不可变链表

给您一个不可变的链表，使用下列接口逆序打印每个节点的值：

ImmutableListNode: 描述不可变链表的接口，链表的头节点已给出。

您需要使用以下函数来访问此链表（您不能直接访问 ImmutableListNode）：

ImmutableListNode.printValue()：打印当前节点的值。
ImmutableListNode.getNext()：返回下一个节点。

输入只用来内部初始化链表。您不可以通过修改链表解决问题。也就是说，您只能通过上述 API 来操作链表。

解：

1.关键：

（1）其实，逆序本质就是 “后进先出”的栈结构

(2)这里有很多方法，比如先用vec存储再逆序，或者stack存储

(3)这里我采用递归进行逆序输出（递归的本质就是 stack 栈结构）

2.代码：


class Solution {
public:
    void printLinkedListInReverse(ImmutableListNode* head) {
        //递归打印,相当于 一个栈结构
        //（1）出口
        if(head == NULL)
        {
            return ;
        }
        //递归
        printLinkedListInReverse(head->getNext());
        head->printValue();
 
    }
};

T32:判断二叉树中是否存在一条链表

给你一棵以 root 为根的二叉树和一个 head 为第一个节点的链表。

如果在二叉树中，存在一条一直向下的路径，且每个点的数值恰好一一对应以 head 为首的链表中每个节点的值，那么请你返回 True ，否则返回 False 。

一直向下的路径的意思是：从树中某个节点开始，一直连续向下的路径。

解：

1.关键：

（1）利用递归的写法travel（这里是先序，中序和后序都可以）一遍二叉树中的节点，判断是否可以作为链表的第一个节点

(2)如果可以，就对这个节点进行 dfs 深搜，观察是否可以在最深层返回 true, 或者返回false

2.代码


class Solution {
public:
    bool Flag = false;
    bool isSubPath(ListNode* head, TreeNode* root) {
        //二叉树 中是否存在 一条链表值（和搜索 相关）
        //先序 遍历的 同时 ，把 “访问 ” 换成 “dfs搜索即可”
        travel(head,root);
        return Flag;
    }
    void travel(ListNode* head,TreeNode* root)
    {
        //（1）出口
        if(root == NULL)
        {
            return ;
        }
        //(dfs)--只有 root->val == head->val才需要
        if(root->val == head->val)
        {
            if(dfs(root,head))
            {
                Flag = true;
                return ;
            }
        }
        //--递归
        travel(head,root->left);
        travel(head,root->right);
    }
    bool dfs(TreeNode* root ,ListNode* head)
    {
        bool flag=true;
        //不要更改head
        ListNode* tmp = head;
        //(1)出口:
        if(head == NULL)
        {
            //true
            return true;
        }
        else if(head!=NULL && root==NULL)
        {
            return false;
        }
        //case1: root->val 和 head->val 不匹配
        if(root->val != head->val)
        {
            //无需再搜索了
            flag = false;
        }
        else
        {
            //继续 递归
            if(dfs(root->left,tmp->next))
            {
                return true;
            }
            else if(dfs(root->right,tmp->next))
            {
                return true;
            }
            else
            {
                return false;
            }
 
        }
        return flag;
    }
};

T33:二叉树展开为单链表

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同

解：

1.关键：

（1）递归形式的二叉树先序遍历，将“访问” 改为 “链接” 即可

(2)

//核心：任何一个节点只有在经过之后 left和right指针才会被修改，所以

//只要在第一个经过的时候留下原来的 left 和 right指针即可

2.代码：


class Solution {
public:
    TreeNode* pc;
    void flatten(TreeNode* root) {
        //法一：利用O(n)空间，将先序遍历中的访问 改为连接即可
        pc=new TreeNode(0);
        //TreeNode* new_head = pc;
 
        traval(root);
        //他不是看变量root ， 而是看 “那一块内存空间”
    }
    void traval(TreeNode* root)
    {
        //(1)递归出口
        if(root == NULL)
        {
            return ;
        }
        //--先序 连接
        //核心：任何一个节点 只有在经过之后 left和right指针才会被修改，所以
        //只要在 第一个经过的 时候 留下 原来的 left 和 right指针即可
        TreeNode* left_node = root->left;
        TreeNode* right_node =root->right;
 
        pc->right = root;
        pc->left = NULL;
        pc = pc->right;
        //记得将root->right 和 root->left保留下来
        traval(left_node);
        traval(right_node);
    }
};

T34:k个节点一组翻转一条链表

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

解：

1.关键：

（1）朴素就好了，基础就是那个题（一条链表的部分节点的翻转）

(2)第一次特殊处理，得到新的 new_head头节点作为返回值

(3)利用“死循环” 对后续的节点进行 “相同的处理”，重点是2中退出的case，case1是pc->next == NULL,说明上一次已经是 k|n的最后一组了，可以直接返回new_head

case2：如果head2到达了一个NULL,说明不够了，可以直接返回new_head

2.代码：


class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        //特殊:
        if(head == NULL || head->next == NULL || k==1)
        {
            return head;
        }
        //k个一组 进行 链表节点的 翻转
        //没有更好的策略，只能依次翻转
        //设置一个头节点
        ListNode* pc=new ListNode(0);
        pc->next = head;
        //1.第一次翻转，找到left的前一个节点 和 right节点
        //先以 前k个节点为例
        ListNode* head1=pc; //指向left前一个
        ListNode* head2=head; //指向right
        for(int i=1;i<=k-1;i++)
        {
            if(head2 == NULL)
            {
                return head; //原来节点的数量数少于k个
            }
            head2 = head2->next;
        }
        if(head2 == NULL)
        {
            return head;
        }
        //现在 head2 就是right位置的 节点
        //(1)先 让head1->next保留下来 然后更新为 head2-
        ListNode* start = head1->next;
        ListNode* static_start=start;
        head1->next = head2;
        //--翻转 ， 最后 让这个 翻转后的 最后start->next 更新为head2->next
        ListNode* tmp=start->next;
        start->next = head2->next;
        head2->next = NULL ; //记得置空!--用于tmp判断翻转的终点
        while(tmp!=NULL && start!=NULL)
        {
            //cout<<"start:"<<start->val<<endl;
            ListNode* u=tmp->next;
            tmp->next = start;
            start = tmp;
            tmp = u;
        }
        //完成了 依次翻转, 头节点为head1->next
        //几个重要的 指针:
        ListNode* new_head = head1->next;  //可以返回的 “真”头节点
        //下一次开始的left节点的 前一个节点
        pc = static_start;//开始写之后的 循环
        //设计好 循环的 终点  --利用2中情况的break作为循环的退出
        //show(new_head);  //结果显示 第一次交换没问题
        //cout<< "pc:"<<pc->val<<endl; //好吧，pc指向错误
 
        while(1)
        {
            //pc一定不是 NULL，但是 pc->next如果是NULL,即为case1 ，k|n，正好分组
            if(pc->next == NULL)
            {
                break;  //正好分组
            }
            //找到head1 和 head2，如果没有找到head2，就是case2，退出循环
            head1 = pc;
            head2 = pc->next;
            for(int i=1;i<=k-1;i++)
            {
                if(head2 == NULL)
                {
                    return new_head;
                }
                head2 = head2->next;
            }
            if(head2 == NULL)
            {
                return new_head;
            }
            //找到了 head1 和 head2
            ListNode* start = head1->next;
            ListNode* static_start=start;
             //pc->next!=NULL,所以start一定不是NULL
            head1->next = head2;
 
            ListNode* tmp=start->next; 
            start->next = head2->next; //所以它的意思是head2可能为NULL
            head2->next = NULL ; //记得置空!--用于tmp判断翻转的终点
            while(tmp!=NULL && start!=NULL)
            {
                ListNode* u=tmp->next;
                tmp->next = start;
                start = tmp;
                tmp = u;
            }
            pc = static_start;
        }
        return new_head;
    }
    //这个错误 是 第1个节点 一直和后面的节点在交换
    //--辅助 测试函数
    void show(ListNode* head)
    {
        ListNode* tmp =head;
        while(tmp!=NULL)
        {
            cout<<tmp->val<<" ";
            tmp = tmp->next;
        }
        cout<<endl;
    }
};

T35:按照一定严格递减规则删除节点

给你一个链表的头节点 head 。

对于列表中的每个节点 node ，如果其右侧存在一个具有 严格更大 值的节点，则移除 node 。

返回修改后链表的头节点 head 。

解：

1.关键：

（1）思路：翻转 + 快慢指针遍历，打擂台删除节点 + 翻转

(2)学会转化，因为前面看不到后面有啥，不如先翻转，逆向思维进行考虑

2.代码：


class Solution {
public:
    ListNode* removeNodes(ListNode* head) {
        //特殊:
        if(head == NULL || head->next== NULL)
        {
            return head;
        }
        //先翻转， 然后设置一个max打擂台，如果 后续节点有比max严格小的节点
        //就利用快慢（相隔为1）指针删除该节点
        //最后再翻转 依次，并且返回 翻转后的头节点
        //(1)第一次翻转
        head = reverse(head);
        //(2)遍历依次 打擂台 + 快慢指针删除节点
        ListNode* fast = head->next;
        ListNode* slow = head;
        int max = slow->val;
        while(fast!=NULL)
        {
            if(fast->val < max)
            {
                //删除fast节点
                fast=fast->next;
                slow->next = slow->next->next;
                continue;
            }
            else
            {
                //是否需要更新max
                if(fast->val > max)
                {
                    max = fast->val;
                }
                fast = fast->next;
                slow = slow->next;
            }
        }//此时fast已经指向NULL
        //(3)再次翻转
        head = reverse(head);
        return head;
    }
 
    //--辅助翻转函数 ， 返回翻转之后的 头节点
    ListNode* reverse(ListNode* head)
    {
        //特殊:
        if(head ==NULL || head->next == NULL)
        {
            return head;
        }
        //--一般
        ListNode* start = head;
        ListNode* tmp = start->next;
        start->next =NULL;
        while(tmp!=NULL && start!=NULL)
        {
            ListNode* u = tmp->next;
            tmp->next = start;
            start = tmp;
            tmp = u;
        }
        return start;
    }
};

T36:对按照绝对值升序排序的链表进行按照值排序

给你一个链表的头结点 head ，这个链表是根据结点的绝对值进行升序排序, 返回重新根据节点的值进行升序排序的链表。

解：

1.关键：

（1）为了方便访问，先改用一个 vec1存储所有的数值

(2)“按照绝对值排序”有一些特点和规律，本质就是把负数和非负数分开来观察：

可见，负数其实后面的更小，非负数前面的更小

（3）分成2次遍历vec1 分别取出负数和非负数，然后按照从小到大的次序存储到 vec2中,最后遍历依次链表并且修改链表的数值即可

2.代码


class Solution {
public:
    ListNode* sortLinkedList(ListNode* head) {
        //特殊:
        if(head == NULL || head->next ==NULL)
        {
            return head;
        }
        //（1）先遍历依次 将数值存储到vec1中
        //（2）然后 从后 向前 只取负数 存储到vec2中
        //(3)然后 从前 往后 遍历vec1 取出>=0 的数字 存储到vec2中
        //(4)最后 按照 vec2中的数值 更新链表的 数值
        vector<int> vec1;
        //(1)
        ListNode* tmp = head;
        while(tmp !=NULL)
        {
            vec1.push_back(tmp->val);
            tmp=tmp->next;
        }
        //(2)
        int size= vec1.size();
        vector<int> vec2;
        for(int i=size-1;i>=0;i--)
        {
            if(vec1[i] < 0)
            {
                vec2.push_back(vec1[i]);
            }
        }
        //(3)
        for(int i=0 ;i <=size-1;i++)
        {
            if(vec1[i] >= 0)
            {
                vec2.push_back(vec1[i]);
            }
        }
        //(4)
        tmp = head;
        for(int i=0;i<=size-1;i++)
        {
            tmp->val = vec2[i];
            tmp= tmp->next;
        }
        return head;
    }
};

T37:删除排序链表中的重复节点

给定一个已排序的链表的头 head ， 删除所有重复的元素，使每个元素只出现一次 。返回 已排序的链表 。

解：

1.关键：

（1）利用相隔为1的快慢指针进行判断

(2)如果fast->val == slow->val ，就删除这个fast节点

2.代码：


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //利用 相隔为1的 快慢指针进行删除
        //特殊:
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        //--一般:
        ListNode* fast = head->next;
        ListNode* slow = head;
        while(fast!=NULL)
        {
            if(fast->val == slow->val)
            {
                //删除fast节点
                fast = fast->next;
                slow->next = slow->next->next;
                continue;
            }
            else
            {
                fast = fast->next;
                slow = slow->next;
            }
        }
        return head;
    }
};

T38:多项式链表求和

多项式链表是一种特殊形式的链表，每个节点表示多项式的一项。

每个节点有三个属性：

coefficient：该项的系数。项 9x4 的系数是 9 。
power：该项的指数。项 9x4 的指数是 4 。
next：指向下一个节点的指针（引用），如果当前节点为链表的最后一个节点则为 null

解：

1.关键：（这是一道上课 ppt的题目）

（1）构建一个新的指针 p3用来指向已经链接好的最后一个节点

(2) p1 和 p2 指针分别指向 list1 和 list2 遍历的最新的那个节点

(3)遍历终止条件就是 p1==NULL or p2 == NULL ,

（4）每次都是比较2者的系数然后分情况讨论

2.代码：


class Solution {
public:
    PolyNode* addPoly(PolyNode* poly1, PolyNode* poly2) {
        //上课的最后一题
        //它是用的 原地 串联法
        //分情况：case1，p1->power 更大 ，case2:power相等， case3：p2的power更大
        //其中case2中 还要分情况考虑 coef之和为0与否
        PolyNode* p1=poly1;
        PolyNode* p2=poly2;
        PolyNode* p3=new PolyNode(0,0);
        PolyNode* new_head=p3;
        while(p1!=NULL && p2!=NULL)
        {
            //(1)比较power
            if(p1->power > p2->power)
            {
                p3->next = p1;
                p1= p1->next;
                p3=p3->next;  //p3始终指向已经链接好的 最后一个节点
            }
            else if(p1->power < p2->power)
            {
                p3->next = p2;
                p2 = p2->next;
                p3 = p3->next;
            }
            else{
                //power相等
                int coef_sum = p1->coefficient + p2->coefficient;
                //case1:
                if(coef_sum != 0)
                {
                    p1->coefficient = coef_sum;
                    p3->next = p1;
                    p1 = p1->next;
                    p3 = p3->next;
                    p2 = p2->next;
                }
                else{
                    //这2个节点都不要了
                    p2 = p2->next;
                    p1 = p1->next;
                }
            }
        }
        //收尾：
        if(p1 != NULL)
        {
            p3->next = p1;
        }
        else if(p2 !=NULL)
        {
            p3->next = p2;
        }
        else{
            p3->next = NULL;
        }
        return new_head->next;
    }
};

T39:"两两交换"一条链表中相邻节点

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

解：

1.关键：

(1)一种链表结构的重要意识，设置好一个永远指向已经交换好的部分的最后一个节点指针pc

（2）然后就是以head == NULL or head->next == NULL 为结束标志的遍历，注意next指针修改的次序

2.代码：


class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        //特殊:
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        //交换 相邻的 节点
        //(1)设置一个 交换好的部分的 最后一个节点的 指针pc
        ListNode* pc = new ListNode(0);
        ListNode* new_head = pc;
        ListNode* tmp = head;  //tmp 永远记录下一次开始的 第一个节点指针
        //(2)
        //cout<<"来过吗"<<endl;
        while(head!=NULL && head->next!=NULL)
        {
            tmp = head->next->next;  //保留 head->next->next
            pc->next = head->next;   //pc先链接到head->next
            pc = pc->next;           //pc到达next
            pc->next = head;         //pc再链接到head
            pc = pc->next;           //pc到next
            head = tmp;             //新的开始点给到head
        }
        if(head == NULL)
        {
            pc->next = NULL;
        }
        else
        {
            pc->next = head;
            head->next = NULL;
        }
 
        return new_head->next;
    }
    //--辅助函数
    void show(ListNode* head)
    {
        ListNode* tmp = head;
        while( tmp !=NULL)
        {
            cout<<tmp->val<<" ";
            tmp = tmp->next;
        }
        cout<<endl;
    }
};

T40:只保留链表中没有重复的数字

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

解：

1.关键：

（1）借鉴之前的删除重复节点的思想，这里采用创新的 “快中慢 ”三个指针的思想进行遍历删除

(2)slow--指向已经处理好的部分的最后一个节点

mid--指向下一次需要比较的第一个节点

fast--指向mid之后的节点，它的值需要和mid节点的值进行比价

2.代码：


class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        //特殊:
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        //这一次 需要删除所有 只要出现重复的 数字
        //我建议 使用 fast mid slow 三指针"快中满"
        //slow -- 永远指向 已经处理好的部分的 最后一个节点 
        //mid -- 指向 下一个部分的 第一个节点  即slow->next
        //fast -- 一路高歌
        ListNode* pc = new ListNode(0);
        ListNode* slow = pc;
        pc->next = head;
        ListNode* mid = pc->next;
        ListNode* fast = mid->next;
        //遍历
        while(fast!=NULL)
        {
            //存下这一次的 mid的val
            int compare_val = mid->val;
            if(fast->val != compare_val)
            {
                //不相等:
                slow = mid;
                mid = fast;
                fast =fast->next;
                continue;
            }
            while(fast!=NULL && fast->val == compare_val)
            {
                fast = fast->next;
            }//出来的时候，fast要么为一个新的val，要么就是NULL
            slow->next = fast;
            mid = fast;
            if(fast == NULL)
            {
                break;
            }
            fast = mid->next;
        }
        return pc->next;
    }
  
};

T41:链表中下一个更大的节点

给定一个长度为 n 的链表 head

对于列表中的每个节点，查找下一个 更大节点 的值。也就是说，对于每个节点，找到它旁边的第一个节点的值，这个节点的值 严格大于 它的值。

返回一个整数数组 answer ，其中 answer[i] 是第 i 个节点( 从1开始 )的下一个更大的节点的值。如果第 i 个节点没有下一个更大的节点，设置 answer[i] = 0 。

解:

法一：朴素暴力搜索法

1.关键：模拟题目要求，对于当前的这个节点 head 依次向后去找比它大的节点

2.代码:


class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        //特殊 :
        if(head->next == NULL )
        {
            return {0};
        }
        //法一： 最朴素的 方法 ， 利用 双层 循环进行 暴力搜索
        ListNode* tmp = head;
        vector<int> ans;
        while(head->next!=NULL)
        {
            tmp = head->next;
            int flag = 0;
            int num_head = head->val;
            while(tmp!=NULL)
            {
                int num_tmp = tmp->val;
                if(num_tmp > num_head)
                {
                    ans.push_back(num_tmp);
                    flag = 1;
                    break;
                }
                tmp= tmp->next;
            }
            if(flag == 0)
            {
                ans.push_back(0);
            }
            head = head->next;
        }
        ans.push_back(0);
        return ans;
    }
};

法二：借鉴讨论区的思路 -- “单调栈！”(有点贪婪思想的味道)

1.关键

(1) 遍历一次，将链表中的元素存储到 vec中，方便访问

(2)从后向前遍历 , 利用一个stack栈作为工具，分情况讨论

case1: 如果 stack为空，说明ans中该位置只能填0

case2:依次检索栈顶top元素，如果比tmp_val大，就说明是“它”，填入ans，同时把tmp_val入栈

case3:如果"不比" tmp_val大，记得出栈

2.代码：


class Solution {
public:
    vector<int> nextLargerNodes(ListNode* head) {
        //借助贪婪算法的 思想 设计一个 “单调栈结构”
        stack<int> Stack;
        //(1)先 遍历一次 ， 然后 从后 往前 进行 搜素
        vector<int> vec;
        while(head!=NULL)
        {
            vec.push_back( head->val);
            head = head->next;
        }
        int size = vec.size();
        vector<int> ans(size,0);
        //(2)然后 从后 往前进行搜索
        //分析：先从 栈顶开始遍历，如果 找比当前位置更大的 值， ans中对应位置填它
        //如果“<=”当前位置的 值， 就出栈
        //如果栈为空， 对应ans中 当前位置 填0 ，然后 将这个val入栈,继续遍历下一个位置
        for(int i =size-1 ;i >=0 ;i--)
        {
            int tmp_val = vec[i];
            int flag = 0;  //flag == 0,代表栈 已空 
            while(!Stack.empty())
            {
                //栈非空,一次检查栈顶
                int top = Stack.top();
                if(top > tmp_val)
                {
                    ans[i] = top;
                    //nice , 记得入栈
                    Stack.push(tmp_val);
                    flag= 1;
                    break;
                }
                else
                {
                    //出栈
                    Stack.pop();
                }
            }
            if(flag == 0)
            {
                //入栈，并且 ans中对应位置填0
                Stack.push(tmp_val);
                ans[i] = 0;
            }
        }
        return ans;
    }
};

T42:找出极值点之间的最小和最大距离

链表中的 临界点 定义为一个 局部极大值点 或 局部极小值点。

如果当前节点的值 严格大于 前一个节点和后一个节点，那么这个节点就是一个 局部极大值点 。

如果当前节点的值 严格小于 前一个节点和后一个节点，那么这个节点就是一个 局部极小值点 。

注意：节点只有在同时存在前一个节点和后一个节点的情况下，才能成为一个 局部极大值点 / 极小值点 。

给你一个链表 head ，返回一个长度为 2 的数组 [minDistance, maxDistance] ，其中 minDistance 是任意两个不同临界点之间的最小距离，maxDistance 是任意两个不同临界点之间的最大距离。如果临界点少于两个，则返回 [-1，-1] 。

解：（比较朴素的方法，以后有更好的想法再加以补充）

1.关键:

(1)转存到 vec中

(2)然后遍历一次，找到那些符合极值点的下标存到ans数组中

(3)最后遍历一次ans数组找到最小距离min

2.代码:


class Solution {
public:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        //特殊:
        if(head == NULL || head->next ==NULL)
        {
            return {-1,-1};
        }
        //返回2个临界节点之间的 最小距离 和 最大距离
        //(1)先转存到vec中
        vector<int> vec;
        while(head!=NULL)
        {
            vec.push_back(head->val);
            head = head->next;
        }
        //(2)遍历一次，如果是临界点，记录将下标 丢到一个ans的数组中
        vector<int> ans;
        int size= vec.size();
        for(int i=1;i<=size-2;i++)
        {
            if((vec[i] > vec[i-1] && vec[i] > vec[i+1])||(vec[i] < vec[i-1] && vec[i] < vec[i+1]))
            {
                //是第i个点 是临界点
                ans.push_back(i);
            }
        }
        //(3)检查ans数组:
        int size2= ans.size();
        if(size2 < 2 )
        {
            return {-1,-1};
        }
        //max容易找但是min似乎需要遍历
        int max = ans[size2-1] - ans[0];
        int min=max;
        //打擂台
        for(int i=1;i<=size2-1;i++)
        {
            if(ans[i] - ans[i-1] < min)
            {
                min = ans[i] - ans[ i-1];
            }
        }
        return {min,max};
        
    }
    
};

T43:对一条链表进行分组，然后翻转其中偶数节点的组

给你一个链表的头节点 head 。

链表中的节点 按顺序 划分成若干非空组，这些非空组的长度构成一个自然数序列（1, 2, 3, 4, ...）。一个组的长度就是组中分配到的节点数目。换句话说：

节点 1 分配给第一组
节点 2 和 3 分配给第二组
节点 4、5 和 6 分配给第三组，以此类推

注意，最后一组的长度可能小于或者等于 1 + 倒数第二组的长度 。

反转每个偶数长度组中的节点，并返回修改后链表的头节点 head

解:（借助vec数组进行偷懒！！哎，没办法，现在的我还是太菜了）

1.关键：

（1）将链表转存到 vec中

(2)这个题目考察的是数学中的 “高斯求和公式 ”n*(n+1)/2的一些处理

(3)对那些分组为偶数的部分找到起点和终点后进行对撞指针的翻转操作

(4)最后将 vec中的数组再存储回到链表中即可

2.代码：


class Solution {
public:
    ListNode* reverseEvenLengthGroups(ListNode* head) {
        //特殊 :
        if(head == NULL || head->next == NULL)
        {
            return head;
        }
        //虽然可以 直接按照 翻转链表的 思想进行处理，
        //但是 需要结合长度的 判断， 感觉比较麻烦 -- 直接 考虑转存到 vec中
        //最后 再根据vec中的数值 构造一条 新的链 / 或者 修改原链表的val
        //(1)转存
        vector<int> vec;
        ListNode* tmp = head;
        while(tmp!=NULL)
        {
            vec.push_back(tmp->val);
            tmp = tmp->next;
        }
        //(2) 根据题目要求 对 vec进行 变换
        //分组 然后 翻转 偶数节点数的部分 -- 直接利用对撞指针 就可以 修改vec数组
        int size= vec.size();
        //其实 就是 高斯求和n* (n+1)/2 ，n=(sqrt(8*k+1)-1)/2向下取整，然后就是剩余的最后一组的 元素的 个数
        int n = (sqrt(8*size+1)-1)/2;
        int remain = size - (n*n + n)/2;
        //每一个偶数部分的 起点 和  终点 都可以 利用数学公式进行计算
        //最后 对 remain进行判断即可
        //起点 (i-1)*i/2 终点 i*(i+1)/2-1
        for(int i=2;i<=n;i+=2)
        {
            int start = (i-1)*i/2;
            int end = i*(i+1)/2-1;
            //翻转 从start 到 end 下标 之间的 数值
            while(end > start)
            {
                swap(vec[start],vec[end]);
                start++;
                end--;
            }
        }
        //这个for循环中 有问题 , 应该是 起点 和 终点 找错了
        if(remain % 2 ==0)
        {
            int end = size-1;
            int start = size-remain;
            while(end > start)
            {
                swap(vec[start],vec[end]);
                start++;
                end--;
            }
        }
        //修改原来链表中的所有数值val
        tmp = head;
        for(int i=0;i<size;i++)
        {
            tmp->val = vec[i];
            tmp = tmp->next;
        }
        return head;
        
    }
};

T44: 删除重复出现的节点（无需连续）

编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。

解：

1.关键：

（1）Set容器 + 快慢指针即可

2.代码：


class Solution {
public:
    ListNode* removeDuplicateNodes(ListNode* head) {
        //tmd看错题了，原来 不需要连续，只要重复出现立刻删除这个节点
        //利用set + 快慢指针即可
        //特殊:
        if(head == NULL|| head->next ==NULL)
        {
            return head;
        }
        //
        unordered_set<int> Set;
        //(1)遍历 + 快慢指针
        ListNode* fast = head->next;
        ListNode* slow = head;
        Set.insert(slow->val);
        while(fast!=NULL)
        {
            //可能需要删除fast这个节点
            if(Set.count(fast->val))
            {
                slow->next = fast->next;
                fast = fast->next; // 删除 节点 fast
            }
            else
            {
                Set.insert(fast->val);
                slow = slow->next;
                fast = fast->next;
            }
        }
        return head;
    }
};

T45.利用一个链表的数值对一个矩阵进行螺旋填充

给你两个整数：m 和 n ，表示矩阵的维数。

另给你一个整数链表的头节点 head 。

请你生成一个大小为 m x n 的螺旋矩阵，矩阵包含链表中的所有整数。链表中的整数从矩阵 左上角 开始、顺时针 按螺旋顺序填充。如果还存在剩余的空格，则用 -1 填充。

返回生成的矩阵。

解：

1.关键：

（1）设置好 up down left right 4个边界，并且在循环中不断更新，注意 x的方向（反直觉），其中down从1开始！

(2)

//内层：；以下标是否到达边界位置为准<=

//外层：以head访问的位置是否为NULL为标准

（3）分4个方向按照一定的顺序进行填充，特别，一个方向完成后，记得更新边界值 + 跳到下一次开始的位置

2.代码：


class Solution {
public:
    vector<vector<int>> spiralMatrix(int m, int n, ListNode* head) {
        //用一个 链表的数值 对 一个 矩阵 进行螺旋填充
        //总的来说就是 利用 一个 路径的 设计 然后 遍历一个 链表
        //我觉得可以 设计up down left right 4个 二维数组访问边界，然后
        int up=m-1 , down = 1 , left = 0 ,right =n-1;//这些边界 都是 从0开始的下标边界
        //每次按照一定的 方向对 二维数组进行填充
        //填充方向:右 - 下 - 左 - 上
        //(1)利用-1对二维数组进行初始化
        vector<vector<int>> vec(m,vector<int>(n,-1));  //m行  n 列
        //利用2层 while循环:
        //内层：；以 下标 是否到达边界位置为准<=
        //外层： 以head访问的 位置是否 为NULL为标准
        int x=0,y=0;  //x行 y 列
        while( head!=NULL)
        {
            //记得 每次需要 更新4个边界的 数值
 
            //(1) y++ ，while循环 ， 向右填充 , 右边界right
            while(head!=NULL && y<=right)
            {
                int val = head->val;
                head = head->next;
                vec[x][y] = val;
                y++;
            } 
            x++;
            y--; //防止越界
            right--;//更新边界
            
            //(2)x++ ,while循环 ，向高的行数填充， 边界up
            while(head!=NULL && x<=up)
            {
                int val = head->val;
                head = head->next;
                vec[x][y] =val;
                x++;
            }
            y--;
            x--;
            up--; //更新 up行数边界
            //(3)y--,while循环， 向左 填充，边界left
            while(head!=NULL && y>=left)
            {
                int val = head->val;
                head = head->next;
                vec[x][y] = val;
                y--;
            }
            x--;
            y++;
            left++; //更新 左边界
            //(4)x--, while循环  ，向 低 行数 填充， 边界 down
            while(head!=NULL && x>=down)
            {
                int val = head->val;
                head = head->next;
                vec[x][y] = val;
                x--;
            }
            y++;
            x++;
            down++;
 
 
        }
        return vec;
    }
};

T46: 将二叉树通过中序遍历得到一个链表

二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

返回转换后的单向链表的头节点。

1.关键：

（1）还是调用递归形式的中序遍历

(2)将 “访问” 修改为：！逻辑：当代码执行到这一步时，说明 root节点的左节点已经访问过了，但是右节点还没有访问过，先将 root 链接到全局链表上，然后再去访问root的right节点

2.代码


class Solution {
public:
    TreeNode* f;
    TreeNode* convertBiNode(TreeNode* root) {
        f= new TreeNode(0);
        TreeNode* pre= f;
        dfs(root);
        return pre->right;
    }
    void dfs(TreeNode* root)
    {
        if(root == NULL)
        return ;
        dfs(root->left);
        f->right = root;
        root->left = NULL;
        f = f->right;
        dfs(root->right);
    }
};

T47:合并val为0之间的节点，并且保证合并之后的链表中没有val为0的节点

给你一个链表的头节点 head ，该链表包含由 0 分隔开的一连串整数。链表的开端和末尾的节点都满足 Node.val == 0 。

对于每两个相邻的 0 ，请你将它们之间的所有节点合并成一个节点，其值是所有已合并节点的值之和。然后将所有 0 移除，修改后的链表不应该含有任何 0 。

返回修改后链表的头节点 head 。

解：

1.关键：

(1)利用 “快慢指针” 加以实现

(2)slow指针，每次指向 “开始0”的前一个节点，然后再让fast指针向前探索

2.代码：


class Solution {
public:
    ListNode* mergeNodes(ListNode* head) {
        //保证 开头 和 结尾的2个节点的val都为0
        //将 val=0 之间的节点的数值求和，然后 作为一个节点
        //利用 “快慢指针”：slow慢指针 指向“开始0”的前一个节点，fast快指针不断向前
        ListNode* new_head = new ListNode(0);
        new_head->next = head;
        ListNode* slow = new_head;
        ListNode* fast = head;
        while(slow!=NULL && slow->next!=NULL)  //先以 slow！=NULL作为结束条件
        {
            //(1)当slow->next->val == 0的时候 ，就可以开始合并了
            if(slow->next->val == 0) // !!注意，slow->next??可能为NULL
            {
                fast = slow->next->next;
                //--开始移动fast--不对，应该要fast 最后的位置处于0
                int sum= 0;
                while(fast!=NULL && fast->val!=0)
                {
                    sum += fast->val;
                    fast = fast->next;
                }
                if(sum == 0) //无论fast == NULL or fast->val == 0都可以
                {
                    //
                    slow->next = fast; //跳过中间的一些值
                }
                else //无论 fast==NULL 或者fast->val == 0都可以
                {
                    //创建一个新的节点连接到slow 和 fast之间
                    ListNode* new_node= new ListNode(sum);
                    slow->next = new_node;
                    new_node->next = fast;
                }
            }
            //这里只要移动slow指针即可
            slow = slow->next;
        }
        return new_head->next;
    }
};

T48: 判断一个给定的字符串string是否为一个小数或者一个整数（似乎和链表没关系）

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

若干空格
一个小数或者整数
（可选）一个 'e' 或 'E' ，后面跟着一个整数
若干空格

小数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
下述格式之一：
1. 至少一位数字，后面跟着一个点 '.'
2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

（可选）一个符号字符（'+' 或 '-'）
至少一位数字

部分数值列举如下：

["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4

解：

1.关键：

（1）这个题目就是按照题干的要求不断判断当前检测的字符是否符合要求

(2) 怎么说呢？反正就是有序的一些 if判断，只要有一点不满足就直接返回false ,同时注意结合辅助函数的调用（尤其是那个判断substr是否全部为空格的函数）

2.代码：


class Solution {
public:
    bool isNumber(string s) {
        //看来是我误会了， 如果是空格不能 两边都有东西
        //看来空格两边必须有一个全部为空格
        
        //判断一个 字符串 是否 表示一个 正数 或小数, 返回true or false;
        //从s[0] 一致判断到 s[size-1]多个if 中只要 1个 false直接false
        int size= s.size();
        //特殊:
        if(size == 1)
        {
            if(is_num(s[0]))
            {
                return true;
            }
            else{
                return false;
            }
        }
        int num_flag=0; // ==1代表已经出现过数字
        int dot_flag = 0; //dot_flag=1 代表小数点已经出现一次了
        for(int i=0 ;i<=size-1 ;i++)
        {
            //(-1)其它字符，字节false
            if(is_else_char(s[i]))
            {
                return false;
            }
            //(0)如果遇到的 是一个符号
            if(s[i]=='+' || s[i] == '-')
            {
                if(num_flag ==1)
                {
                    return false;
                }
                else 
                {
                    continue;
                }
            }
            //（1）如果 遇到 空格，直接continue
            if(s[i] == ' ')
            {
                if((!is_all_blank(s.substr(0,i))) && (!is_all_blank(s.substr(i+1,size-i-1))))
                {
                    return false;
                }
                else{
                    continue;
                }
            }
            //(2)如果是e 后面必须接一个 整数
            if(s[i]=='e' || s[i]=='E')
            {
                if(i==size-1 || is_all_blank(s.substr(i+1,size-i-1)))
                {
                    return false;
                }
                if(num_flag == 0)
                {
                    return false;
                }
                cout<<is_integer(s.substr(i+1,size-i-1))<<endl;
                cout<<"果然是这里"<<endl;
                //说明 is_integer这个 函数 返回值有问题,
                //此时i==3
                return is_integer(s.substr(i+1,size-i-1));
            }
            //(3)如果是 num okcontinue
            if(is_num(s[i]))
            {
                num_flag =1;
                continue;
            }
            
            //(4)如果是 小数点 
            if(s[i] == '.')
            {
                if(dot_flag == 1)
                {
                    return false;
                }
                //1.前面是数字
                if(i>0 && is_num(s[i-1]))
                {
                    dot_flag = 1;
                    continue;
                }
                //2.后面是数字
                if(i!=size-1 && is_num(s[i+1]))
                {
                    dot_flag = 1;
                    continue;
                }
                //3.后面是e和一个整数 ok
                if(i>0 && is_num(s[i-1]) && i<=size-3 && (s[i+1]=='e' || s[i+1]=='E') && is_integer(s.substr(i+2,size-i-2)))
                {
                    
                    return true;
                }
                //cout<<"是这里返回的false吗?"<<endl; --不是
                return false;
            }
        }
        if(num_flag == 0)
        {
            return false;  //没出现数字，不行
        }
        return true;
    }
    
    //辅助函数
    //判断 是出现了 规定之外的字符
    bool is_else_char(char ch)
    {
        if(ch == 'e' || ch=='E')
        {
            return false;
        }
        if(ch <= '9' && ch>='0')
        {
            return false;
        }
        if(ch == '+'|| ch == '-')
        {
            return false;
        }
        if(ch == ' '|| ch=='.')
        {
            return false;
        }
        return true;
    }
    //判断一个字符串是否为整数
    bool is_integer(string s)
    {
        int size = s.size();
        if(size == 0)
        {
            return false;
        }
        //忘记考虑一种情况了，就是如果 遇到了 “末尾空格” 就可以直接返回true
        //s.substr（start_index,len）返回一个string类型变量
        if(s[0]=='+' || s[0]=='-')
        {
            if(size == 1)
            {
                return false;
            }
            for(int i=1;i<=size-1;i++)
            {
                if(s[i]==' ')
                {
                    return is_all_blank(s.substr(i,size-i));
                }
                if(! is_num(s[i]))
                {
                    return false;
                }
            }
            return true;
        }
        for(int i =0;i<=size-1;i++)
        {
            if(s[i]==' ')
            {
                return is_all_blank(s.substr(i,size-i));
            }
            if(!is_num( s[i]))
            {
                return false;
            }
        }
        return true;
    }
    //设计一个 判断 一个字符串全部为 空格的 辅助函数
    bool is_all_blank(string s)
    {
        int size = s.size();
        for(int i=0;i<=size-1;i++)
        {
            if( s[i]!=' ')
            {
                return false;
            }
        }
        return true;
    }
 
    bool is_num(char ch)
    {
        if(ch <= '9' && ch>='0')
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/我家自动化/article/detail/523693

数据结构：链表 课程总结 + leetcode刷题_将n个数字插入空链表l中,使l形成递减有序链表

数据结构：链表课程总结 + leetcode刷题_将n个数字插入空链表l中,使l形成递减有序链表