526互联

链表中环的入口结点

发布时间 2023-03-24 12:01:32作者: 穿过雾的阴霾

方法1，遍历一次，使用额外空间

  • 哈希直接存储指针出现的次数，如果重复出现，直接返回即可
class Solution {
public:
    unordered_map<ListNode*,int> hashmap;//记录指针及其出现的次数+1
    ListNode *entryNodeOfLoop(ListNode *head) {
        auto p=head;
        int id=1;//因为hashmap默认就是0，如果id初值为0，造成混淆
        while(p)//无环将在这里退出
        {
            if(hashmap[p])
                return p;//有环
            hashmap[p]=id++;
            p=p->next;
        }
        if(p==NULL) return NULL;//无环
    }
};

方法2，遍历一次，常数空间

  • 如果只需要标记该点是否遍历过，那么直接修改值就好
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {

        while(head){
            if(head->val > 1000){
              head->val -= 1000;
              return head;  
            } 
            head->val += 1000;
            head = head->next;
        }
        return NULL;

    }
};

方法3，快慢指针

  • 时间复杂度相同，常数空间
class Solution {
public:
    ListNode *entryNodeOfLoop(ListNode *head) {
        if(head==NULL||head->next==NULL)    return NULL;
        auto i=head;auto j=head;
        while(i&&j)
        {
            //i走一步，j走两步
            i=i->next;
            j=j->next;
            if(j)   j=j->next;
            else return NULL;//无环返回NULL
            if(i==j)//如果两指针相遇，说明有环
            {
                j=head;
                while(i!=j)
                {
                    i=i->next;
                    j=j->next;
                }
                return i;
            }
        }
        return NULL;
    }
};