[TIL] 2022.02.28 연결 리스트

'''
    https://leetcode.com/problems/reverse-linked-list/
'''
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        if head == None:
            return head

        # 노트를 저장할 스택 생성
        stack = []
        curr = head

        # 연결 리스트 순회
        while curr.next != None:

            # 스택에 현재 노트 추가
            stack.append(curr)
            curr = curr.next

        first = curr

        # 스택의 요소를 하나씩 꺼냄
        while stack:

            curr.next = stack.pop()
            curr = curr.next

        curr.next = None

        return first

'''
https://leetcode.com/problems/linked-list-cycle/
'''
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        
        # slow, fast 포인터는 head를 가리킴
        slow = head
        fast = head
        
        while fast != None and fast.next !=None:

            # slow는 1번의 이동을 함
            slow = slow.next
            
            # fast는 2번의 이동을 함
            fast = fast.next.next

            # fast와 slow가 같아진다면 연결 리스트는 순환
            if slow == fast:
                return True

        return False