力扣142.环形链表II 简单遍历即可实现O(n)时间+O(1)空间

Problem: 142. 环形链表 II

解题方法

简单遍历 + 怎么表示节点是已访问过的？+ 怎么还原节点值？

• 怎么表示节点是已访问过的：访问过的节点加上一个2*MAX+1，保证访问过的节点的值大于MAX（10^5）；同时计算链表节点总数len。
• 怎么还原节点值：遍历len个节点，每个节点减去一个2*MAX+1

复杂度

时间复杂度:

$O(n)$

空间复杂度:

$O(1)$

Code

const int MAX = 100000;
const int STATE = 2*MAX+1;
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        bool flag=0;// 表示是否有环
        ListNode *tmp=head;
        ListNode *resNode=NULL;
        int len = 0;// 记录链表节点个数
        while(head!=NULL){
            if(head->val>MAX){// 标记这个点已经找过
                flag=1;
                resNode=head;// 记录下需要返回的节点
                break;
            }
            len++;
            head->val+=STATE;// 表示该节点已经被访问过（保证现在节点的值大于MAX）后面减去STATE就是还原
            head=head->next;
        }
        int i=0;//数组的长度就是链表节点个数
        if(flag){
            while(i<len){
                tmp->val-=STATE;// 还原
                tmp=tmp->next;
                i++;
            }
        }
        
        return resNode;
    }
};