[数据结构与算法]872-链表算法题

1、删除问题

递归删除的思路：

1. 先删除，再不断往后递归（迭代思路，手动删除）
2. 先递归到最后，递归的过程制定连接规则；符合的return当前head，不符合的返回head->next，也就是删除了当前head，作为下一次栈弹出的返回值。
3. 写完代码，完整地写出递归调用栈的弹出过程，即可知道递归写的对不对

2.1 删除给定val的结点：leetcode 203/王道链表01,02

五种解题方法：6种写法

1. 带头结点迭代删除：最基础最简单的方法pre->next = pre->next->next;
2. 带头结点递归删除：
   • 递归无返回值写法：先删除，后递归【迭代的思路】，带头结点，删除的结点是next结点，没啥好说的和迭代一样
3. 不带头结点迭代删除：注意head位置删除对于空指针的处理
4. 不带头结点递归删除
   • 递归无返回值写法：先删除，后递归【迭代的思路】 （由于是不带头结点，删除的结点就是当前结点，则可能断链，因此要传入引用！！）
   • 递归有返回值的两种写法：都是先递归到尾，制定连接/删除规则；再从后往前根据弹出返回值head连接

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        // return func1(head, val);
        // return func2(head, val);
        // return func3(head, val);
        // return func4(head, val);
        // return func5(head, val);
        return func6(head, val);
    }

    ListNode* func1(ListNode* head, int val){
        // 1. 带头结点--非递归
        ListNode* dummyNode = new ListNode();
        dummyNode->next = head;
        ListNode* pre = dummyNode;
        while(pre->next != NULL){
            if(pre->next->val == val) 
                pre->next = pre->next->next;
                //注意此时不要p = p->next!!
            else
                pre = pre->next;
        }
        return dummyNode->next;
    }
    ListNode* func2(ListNode* head, int val){
        //2. 带头结点--递归(无返回值，递归只做删除的写法)
        //更好理解，本质是还是迭代处理的思路，只是代码量少了
        ListNode* dummyNode = new ListNode();
        dummyNode->next = head;
        recursion1(dummyNode, val); 
        return dummyNode->next;
    }
    void recursion1(ListNode* dummyNode, int val){
        if(dummyNode->next == NULL)
            return ;
        else if(dummyNode->next->val == val){
            //遇到要删的就删，然后递归下一个结点处理
            dummyNode->next = dummyNode->next->next;
            recursion1(dummyNode, val);
        }
        else
            recursion1(dummyNode->next, val);
    }

    ListNode* func3(ListNode* head, int val){
        /** 3 .不带头结点--迭代删除：麻烦，不用
        注意点：一开始要删除开头连续的val结点，则判断head的几种情况
            1. head为空链表：4中解决了，就不用单独在开头写一个判断
            2. 删除后链表不为空：如661，while结束head指向1，正常
            3. 删除后链表为空：如777，while结束后head为NULL
                若while内条件只有head->val==val，则NULL->val会报错
                因此必须添加判断head != NULL且必须写在前面
            4. while删除后是要做成带头结点删除问题，你这个dummyNone自身不能为空，即while退出时的head不能为空。
                    即3的情况结束后，head=NULL，要单独判断
        **/
        //必须要写head != NULL判断：情况3
        while(head != NULL && head->val == val)
            head = head->next;
        //退出时head指向结点作为dummyNoe，做成带头结点删除问题
        if(head == NULL)    return NULL; // 别忘了！！dummyNode本身不能为空
        ListNode* pre = head; 
        while(pre->next != NULL){
            if(pre->next->val == val) 
                pre->next = pre->next->next;
                //注意此时不要p = p->next!!
            else
                pre = pre->next;
        }
        return head;
    }
    ListNode* func4(ListNode* head, int val){
        // 4. 不带头结点---递归删除(无返回值)
        recursion2(head, val);
        return head;

    }
    void recursion2(ListNode* &head, int val){
        /** 形参传入head的引用&head！！！delete delNode就不会断链
            如1 3 6 2
        一开始传入1的引用，即链表头指针的引用，则你后面不管怎么递归传入，都是在1的引用的基础上操作的，也就是修改的都是原始链表，如：
        recursion2(1, val);
        recursion2(1->next, val);  3
        recursion2(3->next, val); 6

        6位置的原指针：3->next引用传入
            让6 = 6->next 相当于元指针3->next = 3->next->next，
            也就是6已经被断开了，你再free就不会断链

        6位置的副本指针：非引用传入
            不传入引用：6 = 6->next，6的副本指针指向2的位置，但是和原指针3->next无关。也就是如果删除了6，3->next指向位置就空了，但是如果只是修改一些内容，由于6的位置不变，3->next依然能找到，则修改内容依然作用于原链表。只有删除6的情况会出现问题

        **/ 
        if(head == NULL)
            return ;
        else if(head->val == val){
            ListNode* delNode = head;
            head = head->next;
            delete delNode;
            recursion2(head, val);
        }
        else
            recursion2(head->next, val);
    }

    ListNode* func5(ListNode* head, int val){
        /** 5. 不带头结点--递归删除（先递归到尾部，再根据返回值进行连接）
            1-->2->6->3 删除6
        1->next = func(2)
        2->next = func(6)
        6要删除，不能6->next,因此单独处理，6->next的返回值
            2->next = func(6) = func(3)
        3->next = func(NULL) 
        递归栈弹出：
            func(NULL): return NULL
            func(3):
                3->next = func(NULL) = NULL
                return head = 3->NULL
            func(6):
                return func(3) = 3->NULL
        
            func(2):
                2->next = func(6)= 3->NULL
                return head = 2->3->NULL
            func(1):
                1->next = func(2) = 2->3->NULL
                return head = 1->2->3->NULL
        思路：
            先递归到最尾部，规定连接规则，只差每次递归的返回值
            最后通过最后head返回当前链表作为递归返回值，再一步步弹出栈连接前面的结点
        **/
        if(head == NULL)
            return head;
        else if(head->val == val)
            return func5(head->next, val);
        else    
            head->next = func5(head->next, val);
         //类似树的后序，这个head是全部递归结束后退出返回的
        return head;
    }

    ListNode* func6(ListNode* head, int val){
        /**
        如 1 2 6 4 3删除6
        递归栈弹出过程：
        func(3)
            3->next = func(NULL) = NULL
            return 3->NULL
        func(4)
            4->next = func(3) = 3->NULL
            return 4->3->NULL
        func(6)
            6->next = func(4) = 4->3->NULL
            6要删除
            return 6->next = 4->3->NULL
        func(2)
            2->next = func(6) = 4->3->NULL
            return 2->4->3->NULL
        func(1)
            1->next = func(2) = 2->4->3->NULL
            return 1->2->4->3->NULL
        **/
        if(head == NULL)
            return head;
        //先递归到最后
        head->next = func6(head->next, val);
        if(head->val == val)
            return head->next; //用head->next连接，即删除当前head
        return head; //正常连接
    }
};

2.2 删除链表倒数第n个结点 leetcode.19/王道22.

题解

2、逆置链表

leetcode206/王道05. 原地逆置/翻转整个链表

1、迭代法：新建pre结点

p往哪里插：用pre指向p->next位置

新建pre，也相当于头插法新建一个dummyHead

时间复杂度：O(N)：遍历整个链表1次
空间复杂度：O(1)：只需要新建一个pre结点

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head == NULL || head->next == NULL)
            return head;
        ListNode *pre = NULL; //pre指向新链表的第一个元素，原链表当前p的前驱结点
        ListNode *p = head; //当前待插入结点
        ListNode *r; //p后继
        while(p){
            r = p->next;
            p->next = pre; //p逆置：指向原来自己的前驱
            pre = p; // 下一个结点的前驱更新为p
            p = r; //更新p为下一个结点
        }
        return pre; //最后pre指向原链表的最后一个结点
    }
};

2、头插法

p往哪里插：用dummyHead->next指向p->next位置【本质和第一种方法没区别】

时间复杂度：O(N)：遍历整个链表1次
空间复杂度：O(1)：

dummyHead->next = NULL;的两种含义：

• 如果待逆置链表本身是带头结点的，dummyHead->next = NULL;等于把该链表断开成两部分，就用该链表的头结点作为新插入链表。

• 如果待逆置链表本身不带头结点，dummyHead->next = NULL;表示新建了一个带头结点单链表。

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        // 单独处理
        if(head == NULL || head->next == NULL)
            return head;
        ListNode* dummyHead = new ListNode();
        // 单独建一个新的带头结点链表【单链表必须有尾指针为NULL】，把原链表往此链表进行头插
        dummyHead->next = NULL; 
        ListNode* p = head; //当前待头插结点
        ListNode* r = head; //p->next，p通过之前记录的r继续往后遍历
        while(p != NULL){
            r = p->next; //r存放p下一个位置
            p->next = dummyHead->next; //头插1
            dummyHead->next = p; //头插2
            p = r; // p更新
        }
        return dummyHead->next;
    }
};

3、王道03. 逆序输出链表元素. 在leetcode147完成

1、递归

时间复杂度O(N)
空间复杂度O(N)：递归栈

using namespace std;
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        wangdao_02(head); 
        return NULL;
    }

    void wangdao_02(ListNode* head){
        // 王道链表02：逆序输出链表结点值
        // 1. 不带头结点
        func1(head); 

        // 2. 带头结点
        // ListNode* dummyNode = new ListNode();
        // dummyNode->next = head;
        // func2(dummyNode);
    }

    //不带头结点
    void func1(ListNode* head){   
        if(head == NULL)
            return ;
        wangdao_02(head->next);
        printf("%d",head->val);
    }
    
    //带头结点：等于把所有的head换成了duumyNode->next，做成不带头结点一模一样的
    void func2(ListNode* dummyNode){
        if(dummyNode->next == NULL)
            return ;
        func2(dummyNode->next);
        printf("%d", dummyNode->next->val);
    }

};

2. 先逆置链表，再正序输出

时间复杂度：O(N)：逆置链表和正序输出都是O(N)
空间复杂度：O(1):原地逆置不消耗空间

4. 拆分链表

王道10,11，在leetcode完成

using namespace std;
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode* dummyHeadA = new ListNode();
        dummyHeadA->next = head;
        //遍历链表验证结果
        ListNode* headx = wd_11(dummyHeadA);//改成wd_10或d_11
        ListNode* p = headx;
        while (p != NULL){
            printf("%d", p->val);
            p = p->next;
        }
        return  NULL;
    }



    ListNode* wd_10(ListNode* dummyHeadA){
        /** A含奇数，B含偶数 
            完全利用原始A的结点，即序号为奇数的保留在A，序号偶数的结点添加给B
            保留原始顺序
            A中要删除（断开偶数序号结点），则用preA遍历
        **/
        ListNode* dummyHeadB = new ListNode();
        ListNode* tailB = dummyHeadB;
        ListNode* preA = dummyHeadA;
        int i = 0;
        while(preA->next != NULL){
            if(i % 2 == 0){
                tailB->next = preA->next;
                tailB = tailB->next;
                preA->next = preA->next->next;
            }
            else  //注意偶数情况preA不要后移
                preA = preA->next;  
            i += 1;
        }
        tailB->next = NULL; //新链表尾插法最后一定要置空！！！

        return dummyHeadA->next;
        // return dummyHeadB->next;
    }// end wd_10


    ListNode* wd_11(ListNode* dummyHeadA){
        /** 和10的不同在于链表B要逆序，则用头插法
            注意这种原地修改的题目，有两个任务，要处理好指针：
                1. 删除原链表结点
                2. 插入新链表：头插，尾插
        **/
        ListNode* dummyHeadB = new ListNode();
        dummyHeadB->next = NULL; //头插法则可以先处理尾指针了

        ListNode* preA = dummyHeadA;
        ListNode* pA = new ListNode();
        int i = 0;
        while(preA->next != NULL){
            if(i % 2 == 0){
                pA = preA->next; //当前待删除+头插结点
                preA->next = preA->next->next; //必须先连起来！！！
                //头插pA
                pA->next = dummyHeadB->next;
                dummyHeadB->next = pA;
            }//注意偶数情况preA不要后移
            else  
                preA = preA->next;  
            i += 1;
        }// end while
        
        // return dummyHeadA->next;
        return dummyHeadB->next;
    }// end wd_11

};

5. 去重

有序链表：删除多余元素 leetcode 83/王道12

注意递归方法

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // return func1(head);
        return func2(head);
    }

    ListNode* func1(ListNode* head){
        /** 1、迭代法
            特点是有序，思路就是每次判断p和p->next一不一样
            注意点：p-->next可能为NULL
            处理：
                1. while仍然用p != NULL，内部单独判断p->next != NULL
                2. while直接用p->next != NULL
        **/
        ListNode* p = head;
        while(p != NULL){
            if(p->next != NULL && p->next->val == p->val){
            	ListNode* delNode = p->next;
                p->next = p->next->next; //delete p->next
                delete delNode;
            }
            else
                p = p->next;
        }
        return head;
    }// end func1

    ListNode* func2(ListNode* head){
        /** 2. 递归法
        考虑2->3->3->3
        func(3) return 3->NULL
        func(3) 
            3->next = func(3->next=3) = 3->NULL
            本来是3->3->NULL
            if判断3->val = 3->next->val
            return 3->NULL
        func(3)
            同理 return 3->NULL
        func(2)
            2->next = func(2->next) = func(3) = 3->NULL
            return 2->3->NULL
        **/
        //要多考虑head->next !=NULL
        if(head == NULL || head->next == NULL)
            return head;
        head->next = func2(head->next);
        if(head->val == head->next->val)
            return head->next;
        return head;
    }// end func2

};

6. 两个有序链表

王道13~15 leetcode 21

• leetcode 21:合并两升序为1升序，使用原节点
• 王道13：合并两升序为1逆序，使用原节点
• 王道14：找到两有序链表公共元素，new一个新链表存放公共元素，结点都新new
• 王道15：找到两有序链表l1,l2的公共元素，l1存放公共元素。【本题特地写成了含有delete的形式，注意参考】

/**
 * 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* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // return func(l1, l2); //原题
        // return wd_13(l1, l2); 
        // return wd_14(l1, l2);
        return wd_15(l1, l2);
    }

    ListNode* func(ListNode* l1, ListNode* l2){
        if(l1 == NULL && l2 == NULL)
            return NULL;
        ListNode* dummyNode = new ListNode(-101); // new一个头结点
        ListNode* tail = dummyNode; // 定义尾指针tail指向头结点
        // 使用尾插法，把结点插入到新链表的尾部
        while(l1 && l2){
            if(l1->val <= l2->val){
                tail->next = l1;
                l1 = l1->next;
                tail = tail->next;
            }
            else{
                tail->next = l2;
                l2 = l2->next;
                tail = tail->next;
            }
        }
        //新链表最后一个结点一定是原链表最后一个结点因此新链表尾指针不用置空
        if(l1)
            tail->next = l1;
        if(l2)
            tail->next = l2;
        return dummyNode->next;
    }

    ListNode* wd_13(ListNode* l1, ListNode* l2){
        /**本题是两个升序合并为一个降序，使用原有结点
        思路：最后要降序，那直接就要想到用头插法！
        
        最后两个while有点多余，稍微改写一下（王道答案写法省略l1的while）
        if(l1)
            l2 = l1;

        **/
        ListNode* dummyHead = new ListNode();
        dummyHead->next = NULL; //头插法准备
        ListNode* r = new ListNode();

        while(l1 && l2){
            if(l1->val < l2->val){
                r = l1->next;
                l1->next = dummyHead->next;
                dummyHead->next = l1;
                l1 = r;
            }
            else{
                r = l2->next;
                l2->next = dummyHead->next;
                dummyHead->next = l2;
                l2 = r;
            }
        }// l1或l2可能还有剩余，一个个头插
        
        while(l1){
            r = l1->next;
            l1->next = dummyHead->next;
            dummyHead->next = l1;
            l1 = r;
        }// 可改良

        while(l2){
            r = l2->next;
            l2->next = dummyHead->next;
            dummyHead->next = l2;
            l2 = r;
        }
        return dummyHead->next;
    }// end wd_13



    ListNode* wd_14(ListNode* l1, ListNode* l2){
        /** 找到两有序链表公共元素，new一个新链表存放公共元素
        结点自己新建，不破坏l1,l2
        **/
        ListNode* dummyHead = new ListNode();
        ListNode* tail = dummyHead;//don't forget NULL pointer
        while(l1 && l2){
            if(l1->val == l2->val){
                ListNode* newNode = new ListNode(l1->val);
                tail->next = newNode; // 尾插1
                tail = tail->next; //尾插2
                l1 = l1->next; 
                l2 = l2->next;
            }
            else if(l1->val < l2->val)
                l1 = l1->next;
            else
                l2 = l2->next;
        }// end while

        tail->next = NULL;
        return dummyHead->next;
    }// end wd_14



    ListNode* wd_15(ListNode* l1, ListNode* l2){
        /**
            l1保留交集结点，其余删除（王道是new了个新的头，但是结点还是用l1,l2的）
            l1保留交集节点的时候，王道吧l1结点插入到了新的头
            本题写出了释放结点的操作（没比较一对结点，就要考虑释放那个）
        **/
        ListNode* dummyHead1 = new ListNode();
        dummyHead1->next = l1;
        ListNode* pre1 = dummyHead1;
        ListNode* delNode = new ListNode();
        while(pre1->next != NULL && l2 != NULL){
            if(pre1->next->val == l2->val){
                // reserve pre1->next + delete l2
                pre1 = pre1->next;
                delNode = l2;
                l2 = l2->next;
                delete delNode;
            }
            else if(pre1->next->val < l2->val){
                // delete pre1->next + don't move pre1!!!
                delNode = pre1->next;
                pre1->next = pre1->next->next;
                delete delNode;
            }
            else{
                // delete l2 + move l2
                delNode = l2;
                l2 = l2->next;
                delete delNode;
            }
        }// end while l1 || l2没遍历完

        //l1没结束，剩余部分必然不可能可已经结束的l2重合了，全部删除
        while(pre1->next != NULL){
            delNode = pre1->next;
            pre1->next = pre1->next->next;
            delete delNode;
        }
        // l1结束了，那就不用做了，只要释放l2所有节点
        while(l2 != NULL){
            delNode = l2;
            l2 = l2->next;
            delete delNode;
        }

        return dummyHead1->next;
    }// end wd_15

};

真题

2020. 在leetcode147完成

using namespace std;
class Solution {
public:
    ListNode* insertionSortList(ListNode* head) {
        return exam_2020(head);
    }

    ListNode* exam_2020(ListNode* head){
        ListNode* dummyNode = new ListNode();
        dummyNode->next = head;
        //遍历寻找min, max的前驱结点
        ListNode* curNode = dummyNode; //遍历结点
        ListNode* pre_maxNode = dummyNode;
        ListNode* pre_minNode = dummyNode;
        float cur_sum =0, len = 0; // 不能写int

        while(curNode->next != NULL){
            cur_sum += curNode->next->val;
            len += 1;
            if(curNode->next->val > pre_maxNode->next->val)
                pre_maxNode = curNode;
            if(curNode->next->val < pre_minNode->next->val)
                pre_minNode = curNode;
            curNode = curNode->next;
        }

        printf("\nmax:%d\t", pre_maxNode->next->val);
        printf("min:%d\t", pre_minNode->next->val);
        printf("sum:%f\t", cur_sum);

        // new_avg
        float new_avg = (cur_sum - pre_maxNode->next->val - pre_minNode->next->val) / (len-2);
        printf("\n删除后平均值：%.2f", new_avg);

        //delete
        if(pre_maxNode->next == pre_minNode)
            pre_maxNode->next = pre_maxNode->next->next->next;
        else if(pre_minNode->next == pre_maxNode)
            pre_minNode->next = pre_minNode->next->next->next;
        else{
            pre_maxNode->next = pre_maxNode->next->next;
            pre_minNode->next = pre_minNode->next->next;
        }

        /** 验证是否删除成功【打印链表】
            注意: 不能用p=head来遍历，比如4213删除了4，但是是在dummyNode为头的链表上删除了，head指针我们没有释放，依然指向了原本开头4的位置，因为4结点也没有释放
        **/ 
        printf("\n输出删除后链表: ");
        ListNode* p = dummyNode;
        while(p->next!=NULL){
            printf("%d", p->next->val);
            p = p->next;
        }
        
        return dummyNode->next; //删除后新链表
    }// end exam_2020

};

思路

注意点：

1. 元素值各不相同，代表min和max不是同一个结点，这个很重要
2. 计算平均值除法要得到小数值，要doube/double或者float/float,; printf("删除后链表avg：%0.2lf\n", avg);:0.2表示保留两位小数

思路一：遍历链表2次：$O(2N)$

• 遍历原链表，找到最大值并删除，得到链表1
• 遍历链表1，找到最小值并删除，得到链表2
• 遍历链表3，计算平均值

稍微优化下，第三步可以在第一步就求出所有元素和然后减去min和max即可
该方法唯一优点就是：删除思路简单，由于min，max不是同一个结点，删除一个个来就行了

思路二：遍历一次链表即可：$O(N)$

• 遍历原链表做以下事情：
  1. 计算所有元素和
  2. 找到最大值结点p的pre_p
  3. 找到最小值结点q的pre_q
• 计算剩余链表平均值
• 删除min和max结点【考虑二者相对位置】
  • 情况1：->pre_p->p->[…]->pre_q->q->：
    pre_p->next = pre_p->next->next【可以=pre_q】
    pre_q->next = pre_q->next->next
  • 情况2：
    • if(pre_p->next = pre_q):->pre_p->p/pre_q->q->
      pre_p->next = pre_p->next->next->next【同时删除p,q】
    • if(pre_q->next = pre_p): ->pre_q->q/pre_p->p->
      pre_q->next = pre_q->next->next->next【同时删除p,q】