35. Reverse Linked List

문제

연결리스트를 뒤집은 뒤 반환하시오.

Input: head = [1,2,3,4,5]
Output: [5,4,3,2,1]

 

해결 방식 1) 재귀함수 사용

https://leetcode.com/problems/reverse-linked-list/

time complexity : O(N)

space complexity : O(N)

 

- current가 null이면 return

- current.next가 null이면 마지막 노드라는 뜻 => head로 만들기

- recursion으로 연결 리스트 traverse

- 현재 head의 다음 노드의 next 필드에 head 넣기(=head 다음 노드가 head를 가리키게 만들기)

- 현재 head의 next 필드에 null 넣기

def reverseList(self, head):
    if not head or not head.next:
        return head
    current = self.reverseList(head.next)
    
    # 현재 head의 다음 노드가 자기 자신을 가리키게 함 
    head.next.next = head
    
    # 현재 head 노드와 이후 노드 연결을 없앰
    head.next = None
    
    return current

 

 

해결방식 2) while문 사용

GeeksforGeeks - Reverse a linked list 참고

time complexity : O(N)

space complexity : O(1)

 

- prev, current, next 포인터 생성

- prev은 current 전의 노드를, next는 current 다음 노드를 가리킴

- current는 head에서 시작

 

1) current 노드의 next 필드가 prev을 가리키게 함(앞 노드와 연결 끊고 뒷 노드와 연결시켜줌)

2) prev, current, next를 한 칸씩 앞으로 이동시킴

3) current가 None이 될 때까지 1, 2 반복 

4) 실행 중지되면 head가 prev을 가리키게 만듦

def reverseList(head):
    prev = None
    current = head

    while current:
        next = current.next
        # 뒤집히는 시점
        current.next = prev
        prev = current
        current = next

    return prev