【代码随想录】刷题Day4

1.交换链表

24. 两两交换链表中的节点

前后指针实现

1.没有元素或者只有一个元素无意义

2.给出一个前驱prev,以及用来交换的两个节点cur和next

3.我当时是这么想的,如果两个指针一起动,那么就要用cur和next同时判断结束,也许这个条件会比较苛刻(我就烦这种边界条件),所以我觉得动一个指针来判断条件就可以了

4.所以我选择用cur判断,在循环中确定next的指向;prev和cur的更新

5.判断条件就变成了cur是否为空,cur的next是否为空

6.循环进去说明需要交换,所以确定next的指向是cur的next;确定是否更新的是根节点;交换;更新prev,cur进入下一轮

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode* prev = nullptr;
        ListNode* cur = head;
        ListNode* next = head;
        while(cur&&cur->next)
        {
            next=cur->next;
            if(prev==nullptr)
                head=next;
            else
                prev->next=next;
            cur->next=next->next;
            next->next=cur;
            prev=cur;
            cur=cur->next;
        }
        return head;
    }
};

前驱?前驱!触发被动了一样的字眼,我是不是可以用递归做啊🤔

 递归交换

1.首先没有元素或者只有一个元素无意义,过

2.递归函数,确定参数头节点要传,因为会换;前驱next、cur和后继next

3.我们依然可以用一个节点进行判断是否到链表底部,cur是否空或者cur的next为空 -- 对应的就是链表是双数还是单数

4.往下传递归的参数其实只需要更新cur和prev,因为前驱必须确定下来,不然往下找不到了,cur也必须有因为我们的底部条件是靠cur判断的,prev等于现在的cur->next,cur等于cur->next->next,就是都得跨两个节点

5.执行交换的代码,next自然就是cur->next。先看是否需要更新的是头节点其条件是prev是否为nullptr;随后交换,返回即可

class Solution {
public:
    void _swapR(ListNode*& head,ListNode* prev,ListNode* cur,ListNode* next)
    {
        if(cur==nullptr||cur->next==nullptr)
            return;
        _swapR(head,cur->next,cur->next->next,next);
        next=cur->next;
        if(prev==nullptr)
            head=next;
        else
            prev->next=next;
        cur->next=next->next;
        next->next=cur;
        return;
    }

    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        _swapR(head,nullptr,head,head);
        return head;
    }
};

2. 快慢指针

我觉得代码实现很简单,主要是思想

想要找从后往前的数,就应该用快慢指针,先让快的指针走n次,然后快慢指针一起动,快指针到边界,慢指针的下一个就是我们要删除的节点。

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

3.链表相交

面试题 02.07. 链表相交

因为只想时间复杂度为O(N),空间复杂度为O(1)

所以我想的是给他们的长度算出来,做差值,然后长的那个往后走差值个数,这样两个链表同样一个长度往下走,那么只要知道什么时候两个节点地址一样,就返回

class Solution {
public:
    int getListNum(ListNode* root)
    {
        int num = 0;
        while(root)
        {
            root=root->next;
            num++;
        }
        return num;
    }

    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int NA = getListNum(headA);
        int NB = getListNum(headB);
        int gap = abs(NA-NB);
        ListNode* more = headA;
        ListNode* less = headB;
        if(NA<NB)
        {
            less = headA;
            more = headB;
        }
        for(int i=0;i<gap;i++)
        {
            more=more->next;
        }
        while(less!=nullptr&&more!=nullptr&&more!=less)
        {
            more=more->next;
            less=less->next;
        }
        return more;
    }
};

4.环形链表

142. 环形链表 II

哈希表 嘻哈表

讲个笑话,程序员在课本上学到了数据冲突可以用哈希表解决;到面试时,面试官问这个求职的程序员:“当程序员和项目经理发生冲突时要怎么解决”,“使用哈希表”程序员想都没想脱口而出。

使用哈希表可以直观的看到数据是否之前插入过,使用起来很简单,不过哈希表通过红黑树实现的这个背后逻辑才是关键,这里不说明了

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        set<ListNode*> s;
        ListNode* cur = head;
        while(cur)
        {
            if(s.find(cur)!=s.end())
                return cur;
            s.insert(cur);
            cur=cur->next;
        }
        return nullptr;
    }
};

快慢指针

操场上一个跑得快一个跑得慢,最终快的一定会把慢的套圈。这个题目的思路也是一样的

1.定义快慢指针,快指针走两个节点,慢指针走一个节点;其实可以如果真的有环,慢指针不动,快指针以一个节点为单位靠近慢指针

2.只要两个地址碰到一起,那确实是有环,不过题目要我们返回头一个链接上的节点,所以我们需要通过一个数学思想来解决

 最后得到x = (n - 1) (y + z) + z,说明x跟z长度一样

那么从fast和从头节点同时走,会遇到一样的节点

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* cur = head;
        ListNode* fast = head;
        int fastnum = 0;
        ListNode* slow = head;
        int slownum = 0;
        while(fast&&fast->next&&fast->next->next)
        {
            fast=fast->next->next;
            fastnum+=2;
            slow=slow->next;
            slownum++;
            if(slow==fast)
            {
                while(cur!=fast)
                {
                    cur=cur->next;
                    fast=fast->next;
                }
                return cur;
            }
        }
        return nullptr;
    }
};

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>