No tag

Publish Date: 2022-02-11

Word Count: 2k

基础数据结构题型总结

链表

力扣题库

2两数相加

c++关于链表的初始化使用不熟练，基础不扎实

逻辑没理清，卡在循环初始化节点与返回头指针的处理上,先初始化头结点后，后面就不好处理初始化新的节点，如果头结点也加入计算的话。(解决方案:直接返回头结点的下一个节点，头结点不加入计算)

优质思路:
把两个链表一长一短的情况通过三目符(?:)来使得null转换为0，使得其过程泛化，避免多条件判断下的代码冗余

基础:

ListNode() : val(0), next(nullptr) {} //初始化函数

其中:为所做的初始化，即为将0赋值给变量val,将nullptr赋值给变量next

new的作用:

1 指针变量的实体化

声明结构体时为什么不用加struct也不会报错？

指针变量和实变量的区别:

指针变量只存储指向地址，无法存储别的值，普通变量直接使用即可。

调用指针指向的变量成员需要用”->”,调用其他变量的成员使用”.”

19 删除链表的倒数第 N 个结点

个人思路:把给的倒序删除参数n转换成正序参数，然后进行删除。(链表长度+双指针法)

其他思路：

1递归实现

class Solution {
public:
    int cur=0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(!head) return NULL;
       head->next = removeNthFromEnd(head->next,n);
       cur++;
       if(n==cur) return head->next;
       return head;
    }
};

2快慢指针，快指针先走n步，然后快慢一起走，直到快指针走到最后，要注意的是可能是要删除第一个节点，这个时候可以直接返回head -> next

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        if(!head | !head -> next) return NULL;
        ListNode * fast = head, *slow = head;
        for(int i = 0; i < n; i++){
            fast = fast -> next;
        }
        if(!fast){
            return head -> next;    
        }
        
        while(fast -> next){
            fast = fast -> next;
            slow = slow -> next;
        }
        slow -> next = slow -> next -> next;
        return head;
    }
};

3 栈

在遍历链表的同时将所有节点依次入栈。根据栈「先进后出」的原则，我们弹出栈的第 nn 个节点就是需要删除的节点，并且目前栈顶的节点就是待删除节点的前驱节点

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

21. 合并两个有序链表

小失误:没有加break，导致最后只剩下一个链表非null时while循环无法停下。

优化:
1可以只初始化一个表头，其余的拼接原有链表节点即可，不需要额外申请新节点

2最后合并时可以使用三目符减少代码量

其他思路:

递归实现：

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

23. 合并K个升序链表

基础缺乏:

1 结构体的定义:可以像类一样定义么？√

C++中的struct与class比较类似。struct默认访问权限是public，class是private；class有继承，多态机制，而struct没有。

2 STL优先队列的用法未掌握：参数，重载运算符的定义方式，比较函数的定义类型(为什么会重载()?)

优先队列的参数只有第一个type是必须的，后面的容器类型和比较类型会默认生成，如果要定义容器类型，那么比较类型也要定义

operator在类内定义时，参数只需要运算符后面的对象，在类外定义时(友元)，参数个数按正常运算所需个数走。

优先队列如果要自定义排序函数，只能用仿函数，不能用普通函数的指针

仿函数：使一个类的使用看上去像一个函数

返回bool类型的仿函数称为谓词

如果operator()接受一个参数，那么叫做一元谓词

如果operator()接受两个参数，那么叫做二元谓词

为什么会重载():好像默认就是这样，类内重载”<”,类外重载”()”

struct tmp1 //运算符重载<
{
    int x;
    tmp1(int a) {x = a;}
    bool operator<(const tmp1& a) const
    {
        return x < a.x; //大顶堆
    }
};
struct tmp2 //重写仿函数
{
    bool operator() (tmp1 a, tmp1 b) 
    {
        return a.x < b.x; //大顶堆
    }
};
struct Status {
        int val;
        ListNode *ptr;
        bool operator < (const Status &rhs) const {
            return val > rhs.val; //小顶堆
        }
    };
struct comp {
        bool operator()(ListNode* a, ListNode* b) {
            return a->val > b->val;//小顶堆
        }
    };

3移位运算符:”>>1”当时没反应过来

4 记得声明完头结点后给头结点初始化

5 优先队列的比较函数定义还是未明白

6 链表题最重要的一点就是判断节点是否存在

24两两交换链表中的节点

未考虑交换后的末尾已交换的链表保存问题，自己误认为只需要2个指针即可，实际上需要三个，最后一个保存已交换后的链表的地址。

链表的边界判断还是不够熟练

其他思路:

递归

把整个链表看成三个部分，头结点，第二个节点，以及其他部分，交换完后返回第二个节点。边界条件是单个节点或者为空时返回

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return head;
        }
        ListNode* newHead = head->next;
        head->next = swapPairs(newHead->next);
        newHead->next = head;
        return newHead;
    }
};