力扣刷题记录10.15

Last updated on October 16, 2024 am

昨天复习前端，今天继续刷题；学点不熟悉的：树、链表、图。

2024/10/15

笔试*2

（1）链表

1、相交链表

寻找相交节点

方法：缝合两个链表，总能找到。

2、反转链表

迭代法灵活用好三个链表节点：pre，cur，next

递归法一看就头晕，再抄一遍加深印象！！！

（理解题解中的一句话，就是假设链表的其余部分已经被反转，那么如何解决它前面的部分）

注意最开头的那个节点的下一个节点必须指向nullptr。

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

3、回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true;否则，返回 false 。

方法一：遍历一次之后栈存储节点值，时空均为O(n)
方法二：快慢指针，翻转前面一半的链表，慢指针向前，当前指针向后依次比较。空O(1)

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if(!head||!head->next)
            return true;
        ListNode *pre=nullptr,*cur=nullptr,*slow=head,*fast=head;
        while(fast!=nullptr&&fast->next!=nullptr){
            cur=slow;
            slow=slow->next;
            fast=fast->next->next;
            cur->next=pre;
            pre=cur;
        } 
        if(fast)   //对应的是奇数个节点的情况，此时需要跳过中间节点。
            slow=slow->next;
        while(slow){
            if(slow->val!=pre->val)
                return false;
            slow=slow->next;
            pre=pre->next;
            
        }
        return true;
    }
};

我试图在最后比较的时候就去翻转前面的链表，但是出错了……还是得最后比完再翻

方法三：递归，时空均为O(n)

首先要知道链表也可以从后往前遍历，方法是：。。迭代。

private void printListNode(ListNode head) {
    if (head == null)
        return;
    printListNode(head->next);
    cout<<head.val<<endl;;
}

所以思路就是，运用这个迭代的思想，让头跟尾比较。

4、环形链表

检测是否存在环

哈希表法

记住存储的是节点就可。（不是数据！！！）

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> res;
       ListNode *tmp=head;
        while (tmp) {
            if (seen.count(tmp)) {
                return true;
            }
            seen.insert(tmp);
            tmp = tmp->next;
        }
        return false;
    }
};

快慢指针法

（为什么我想到了快慢指针，也想到了判断它们是否相等来判断是否有环，但是就是没想到究竟如何实现嘞。。）

原理：如果有环，快指针进入环中之后慢慢地就会甚至在慢指针后，但是最后一定能追上慢指针。「Floyd 判圈算法」（又称龟兔赛跑算法）；如果没环，fast指针就会先到达最后。

class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(!head||!head->next) return false;
        ListNode *slow=head,*fast=head->next;
        while(slow!=fast){
            if(!fast->nexr||!fast){
                return false;
            }
            slow=slow->next;
            fast=fast->next->next;
        }
        return true;
    }
};