[SAP/C++]Check Circular Linked List

난이도 : 중하

 

문제)

linked list의 head pointer를 input으로 받아 해당 리스트가 circular linked list인지, 아닌지를 반환한다(bool)

 

연결리스트를 한번 복습해봤다

다음에서 보면, 2번이 바로 circular linked list인데

마지막 node의 next가 처음 node를 가리키고있으며, 처음 node는 항상 head포인터에 의해 가리켜지고있다.

즉, 처음 node에서 시작하여 계속해서 next -> next로 탐색하다가, head포인터가 가리키는 노드와 같아지는 때가 오면, circular linked list일 것이고.

 

1번 그림과 같이 탐색중에 NULL을 만나면, circular linked list가 아닐 것! 

 

 

/* Link list Node 
struct Node
{
    int data;
    struct Node* next;
    
    Node(int x){
        data = x;
        next = NULL;
    }
    
}; 
*/



/* Should return true if linked list is circular, else false */
bool isCircular(Node *head)
{


    Node *temp=head; 
    
    //공백리스트
    if(head==NULL){
        return true;
    }
    
    while(temp!=NULL){
        
        //next node가 head라는 것은 맨 처음으로 돌아왔다는 것 -> circle존재
        if(temp->next==head){ 
            return true; 
        }
    temp=temp->next;//다음 노드를 가리키게함
    }
    
    return false;

}

 

공백리스트도 circular linked list인 것은 처음안 사실...

 

포인터의 개념이 헷갈려서! 

*head는 노드구조체를 가리키는 포인터이며, head를 출력해보면 head가 가리키는 첫번째 노드가 저장된 "주소값"이 적혀있다.

그것을 temp라는 노드 구조체를 가리키는 포인터에 대입했으니, (Node * temp = head) 

temp를 출력해보면 이 또한, head의 값인 첫번째 node가 저장된 "주소값"이 적혀있을것이며, 

 

첫번째 step에서 head와 temp는 모두 같은(첫번째) 노드를 가리키고있다!

그 뒤 temp는 next 노드를 가리키게 되니 주소값이 계속 변경될 것이고, 어느시점 NULL이 나오면 linked list

NULL이 나오지 않았는데 head와 같은것을 다시 가리키게되면(첫번째 노드의 주소) circular linked list인 것 

숫자 동그라미는 step