mardi 24 septembre 2019

How would I output this in C++ in my main function, and what functions do I need?

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Note: Do not modify the linked list.

Example 1:
Input: head = [3,2,0,-4], pos = 1

Output: tail connects to node index 1

Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:
Input: head = [1,2], pos = 0

Output: tail connects to node index 0

Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:
Input: head = [1], pos = -1

Output: no cycle

Explanation: There is no cycle in the linked list.

#ifndef LISTNODE_H_
#define LISTNODE_H_
#include <iostream>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL)
            return NULL;
        ListNode *p1 = head, *p2 = head;
        do{
            p1 = p1->next;
            p2 = p2->next;
            if(p2 != NULL)
                p2 = p2->next;
            else
                break;

        }while(p1 != p2 && p2 != NULL);
        if(p2 == NULL)
            return NULL;
        p1 = head;
        while(p1 != p2){
            p1 = p1->next;
            p2 = p2->next;
        }
        return p1;
    }
};

#endif

Aucun commentaire:

Enregistrer un commentaire