Share my stupid C solution


  • 0
    M
    struct ListNode *detectCycle(struct ListNode *head) {
    if (head == NULL || head->next == NULL)
        return NULL;
    
    int reverse(struct ListNode *);
    struct ListNode *slow, *fast;
    
    slow = head, fast = head;
    while (slow && fast) {  // find out whether there is a cycle in the linked list and get one node in the cycle
        slow = slow->next;
        if (fast->next)
            fast = fast->next->next;
        else
            fast = fast->next;
        if (slow == fast)
            break;
    }
    if (fast == NULL)
        return NULL;
    
    int cycle_len, length = 0;
    fast = fast->next;
    cycle_len = 1;
    while (fast != slow) {  // get the length of the cycle
        cycle_len++;
        fast = fast->next;
    }
    
    length = reverse(head); // the length before the cycle is l1, the length of cycle l2, here length = 2*l1+l2;
    reverse(head);
    int position = (length-cycle_len+1)/2;  // get the length before the cycle
    while (position > 1) {
        head = head->next;
        position--;
    }
    return head;
    

    }

    int reverse(struct ListNode *head)
    {
    struct ListNode *prev, *curr, *post;
    int length = 0;

    if (head == NULL)
        return 0;
        
    prev = NULL, curr = head;
    while (curr) {
        post = curr->next;
        curr->next = prev;
        prev = curr;
        curr = post;
        length++;
    }
    return length;
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.