LeetCode [206]: Reverse Linked List

📌 LeetCode [206]: Reverse Linked List

🔗 문제 링크

---

문제 설명 📄

주어진 단일 연결 리스트를 역순으로 뒤집고, 뒤집힌 리스트의 시작 노드를 반환하는 문제입니다.

---

문제 접근 방식 📋

1. 포인터 기반 반복 접근:
   • prev를 사용하여 이전 노드를 추적하고, 현재 노드의 next를 이전 노드로 바꿉니다.
   • temp로 다음 노드를 임시 저장하여 연결을 끊어도 순회를 유지합니다.
2. 종료 조건:
   • 마지막 노드에 도달한 뒤, 역순으로 바뀐 리스트의 시작 노드인 head를 반환합니다.

---

Solution 💻

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

        while head:
            temp = head.next 
            head.next = prev
            prev = head
            if not temp:
                break
            head = temp

        return head

---

시간 복잡도 분석 ⏲️

• 시간 복잡도: (O(n))
  • 연결 리스트의 모든 노드를 한 번씩 순회하며 방향을 변경.
• 공간 복잡도: (O(1))
  • 추가 메모리를 사용하지 않고, 원본 리스트를 수정.