2021-10-10周总结

一、题目总结

二、题目复盘 2.1 Leetcode-25：K 个一组翻转链表 (1) 问题描述

(2) 问题分析

这道题麻烦的很，把我头都整大了，翻转的时候需要记住上一次翻转的尾节点和下一次翻转的头结点。

(3) 问题解决

class Solution {
public:
    ListNode* reverse(ListNode* head, ListNode* nexthead){
        ListNode* prehead = new ListNode();
        prehead->next = nullptr;

        while(head != nexthead)
        {
            ListNode* tmp = head;
            head = head->next;
            tmp->next = prehead->next;
            prehead->next = tmp;
        }

        return prehead->next;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        int count = 0;
        ListNode* prehead = (ListNode*)malloc(sizeof(ListNode));
        prehead->next = head;
        ListNode* pre = prehead;
        ListNode* cur = head;

        while(cur != nullptr)
        {
            count++;
            if(count == k)
            {
                count = 0;
                ListNode* nexthead = cur->next;
                ListNode* tmp = reverse(pre->next, nexthead);
                pre->next = tmp;
                head->next = nexthead;
                pre = head;
                head = nexthead;
                cur = head;
            }
            else
                cur = cur->next;
        }

        return prehead->next;
    }
};

2.2 Leetcode-143：重排链表 (1) 问题描述

(2) 问题分析

这道题看完题目，分析示例1后，发现就是把倒数第k个结点插入到正数第k个结点后面，但是对于单链表来说，不好同时调动正数的和倒数的结点，所以想到用vector容器来存储链表的结点，这样就特别好处理了。

(3) 问题解决

class Solution {
public:
    void reorderList(ListNode* head) {
        vector v;

        for(ListNode* cur = head; cur != nullptr; cur = cur->next)
            v.push_back(cur);
        
        for(int i = 0, j = v.size()-1; i < j-1; i++, j--)
        {
            v[j]->next = v[i]->next;
            v[i]->next = v[j];
            v[j-1]->next = nullptr; 
        }
    }
};

2.3 Leetcode-23：合并K个升序链表 (1) 问题描述

(2) 问题分析

这道题虽然难度是困难，但是做起来十分简单，只要会链表归并，就可以做出来，就是遍历vector，然后依次归并就可。

(3) 问题解决

class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2){
        ListNode* head_l1 = new ListNode(0,l1);
        ListNode* pre = head_l1;
        
        while(l1 !=  nullptr)
        {
            if(l2 == nullptr)
                return head_l1->next;
            
            if(l1->val > l2->val)
            {
                ListNode* tmp = l2;
                l2 = l2->next;
                tmp->next = l1;
                pre->next = tmp;
                pre = tmp;
            }
            else
            {
                pre = l1;
                l1 = l1->next;
            }
        }

        pre->next = l2 != nullptr ? l2 : nullptr;

        return head_l1->next;
    }

    ListNode* mergeKLists(vector& lists) {
        ListNode* L = nullptr;

        for(int i = 0; i < lists.size(); i++)
            L = merge(L, lists[i]);

        return L;
    }
};

2.4 Leetcode-1171：从链表中删去总和值为零的连续节点 (1) 问题描述

(2) 问题分析

这道题当时做的时候，一点思路也没有，看了眼题解，别人写的真好，复盘的时候竟也能想起这个解法：就是遍历两遍链表，第一次遍历将最后一次出现sum值的结点放入到map中，第二次遍历，将头一批出现的sum值的结点指向最后一批出现sum结点的下一个结点，这样就行了，解题思维十分的巧妙。

(3) 问题解决

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* prehead = new ListNode(0,head);
        map m;
        int sum = 0;

        for(ListNode* cur = prehead; cur != nullptr; cur = cur->next)
        {
            sum += cur->val;
            m[sum] = cur;
        }

        sum = 0;
        for(ListNode* cur = prehead; cur != nullptr; cur = cur->next)
        {
            sum += cur->val;
            cur->next = m[sum]->next;
        }

        return prehead->next;
    }
};

2.5 Leetcode-876：链表的中间结点 (1) 问题描述

(2) 问题分析

这道题就十分的简单了，就是利用快慢指针就行。

(3) 问题解决

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;

        while(fast != nullptr && fast->next !=  nullptr)
        {
            fast = fast->next->next;
            slow = slow->next;
        }

        return slow;
    }
};