206. Reverse Linked List

연결 리스트를 반대로 뒤집는 문제다.

Solution

투 포인터를 이용해서 해결했다.
dummy까지 쓰리 포인터인가?ㅎ temp도 포인터도 쳐주나?

1. first의 다음 노드를 dummy에 임시 저장한다.
2. first의 next에 이전 노드를 저장해 방향을 바꾼다.
3. 이전 노드(second)를 한 칸 이동 시키고 first 역시 dummy에 저장해둔 다음 노드로 이동한다.

위의 과정을 끝까지 반복한다.

# 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 not head: return None
        first = head
        second = None
        while first:
            dummy = first.next # 임시 저장
            first.next = second # 이전 노드와 연결
            second = first # 다음 노드로 이동
            first = dummy # 다음 노드로 이동
        return second # first는 None, 뒤집힌 노드의 head는 second

시간 복잡도

연결 리스트의 처음부터 끝까지 이동하므로 O(n)이다.