Remove loop in Linked List(Linked List,two-pointer,algorithm,Data Structures,Algorithms) - 플로이드의 사이클 감지 알고리즘 (Floyd's Cycle Detection Algorithm)

https://www.geeksforgeeks.org/problems/remove-loop-in-linked-list/1?page=1&category=Linked%20List&difficulty=Medium,Hard&sortBy=submissions

Remove loop in Linked List | Practice | GeeksforGeeks

Given the head of a linked list that may contain a loop.  A loop means that the last node of the linked list is connected back to a node in the same list.  So if the next of the previous node is null. then there is no loop.  Remove the loop from the linked list, if it is present (we mainly need to make the next of the last node null). Otherwise, keep the linked list as it is.

Note: Given an integer, pos (1 based index)  Position of the node to which the last node links back if there is a loop. If the linked list does not have any loop, then pos = 0.

The generated output will be true if your submitted code is correct, otherwise, false.

Examples:

Input: Linked list: 1->3->4, pos = 2
Output: true
Explanation: The linked list looks like

A loop is present. If you remove it successfully, the answer will be true. 

Input: Linked list: 1->8->3->4, pos = 0
Output: true
Explanation: 

The Linked list does not contains any loop. 

Input: Linked list: 1->2->3->4, pos = 1
Output: true
Explanation: The linked list looks like 

A loop is present. If you remove it successfully, the answer will be true. 

Expected Time Complexity: O(n)
Expected Space Complexity: O(1)

Constraints:
1 ≤ size of linked list ≤ 105

---

이번엔 Geeks for Geeks 콘텐츠다.

Linked List Medium 난이도를 스근하게 한 번 풀어보도록 함

 

 

1. Python

도저히 모르겠어서 GPT를 좀 썼는데,

플로이드의 사이클 감지 알고리즘 (Floyd's Cycle Detection Algorithm) 를 써야한다고 한다.

 

이런 거는 이런 알고리즘 미리 알고 있는 거 아니면 풀기가 매우 어려울 거 같다.

 

class Solution:
    # Function to remove a loop in the linked list.
    def removeLoop(self, head):
        if not head or not head.next:
            return
        
        slow = head
        fast = head
        loop_found = False

        # Step 1: Detect loop
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:  # Loop detected
                loop_found = True
                break
        
        if not loop_found:
            return  # No loop to remove
        
        # Step 2: Find start of the loop
        slow = head
        prev = None
        while slow != fast:
            prev = fast  # Save the previous node
            slow = slow.next
            fast = fast.next
        
        # Step 3: Remove the loop
        # 'prev' is now the last node in the loop
        while fast.next != slow:
            fast = fast.next
        fast.next = None

 

근데 나는 왜 아래코드가 fail이 뜨는지 당최 모르겠다.

'''
# node class:

class Node:
    def __init__(self,val):
        self.next=None
        self.data=val

'''

class Solution:
    #Function to remove a loop in the linked list.
    def removeLoop(self, head):
        # code here
        # remove the loop without losing any nodes
        if not head or not head.next : return
        
        slow = head
        fast = head
        
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow != fast :
                continue
            # Loop 감지
            else :
                temp = head
                while temp.next != slow.next:
                    temp = temp.next
                    slow = slow.next
                slow.next = None
                break


#{ 
 # Driver Code Starts
# driver code:


class Node:

    def __init__(self, val):
        self.next = None
        self.data = val


class linkedList:

    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, num):
        if self.head is None:
            self.head = Node(num)
            self.tail = self.head
        else:
            self.tail.next = Node(num)
            self.tail = self.tail.next

    def isLoop(self):
        if self.head is None:
            return False

        fast = self.head.next
        slow = self.head

        while slow != fast:
            if fast is None or fast.next is None:
                return False
            fast = fast.next.next
            slow = slow.next

        return True

    def loopHere(self, position):
        if position == 0:
            return

        walk = self.head
        for _ in range(1, position):
            walk = walk.next
        self.tail.next = walk

    def length(self):
        walk = self.head
        ret = 0
        while walk:
            ret += 1
            walk = walk.next
        return ret


if __name__ == "__main__":
    t = int(input())
    for _ in range(t):

        arr = tuple(int(x) for x in input().split())
        pos = int(input())
        n = len(arr)
        ll = linkedList()
        for i in arr:
            ll.add(i)
        ll.loopHere(pos)

        Solution().removeLoop(ll.head)

        if ll.isLoop() or ll.length() != n:
            print("false")
            continue
        else:
            print("true")
        print("~")

# } Driver Code Ends

 

대체 왜지.. 왜 아래처럼 해야만 코드가 pass되는지 모르겠다.

분명 논리적으로 차이가 없어 보이는데;;;

 

2. C++

class Solution {
  public:
    // Function to remove a loop in the linked list.
    void removeLoop(Node* head) {
        // code here
        // just remove the loop without losing any nodes
        Node* slow = head;
        Node* fast = head;
        bool cond = true;
        while(fast && fast->next){
            slow = slow -> next;
            fast = fast -> next -> next;
            if(slow==fast){
                cond = false;
                break;
            }
        }
        if(cond) return;
        Node* temp = head;
        while(temp!=slow){
            temp = temp->next;
            slow = slow->next;
        }
        while(fast->next!=slow){
            fast = fast->next;
        }
        fast->next = NULL;
        
    }
};

 

아무리 생각해도 이상하다.

 

그냥 Geeksforgeeks test case가 이상한 것으로 결론..

 

논리적으로 맞는 거 같은 코드는 그냥 맞다.