[Dart] 206. Reverse Linked List

1. 문제

 

https://leetcode.com/problems/reverse-linked-list/description/?envType=study-plan-v2&envId=leetcode-75

 

 

 

2. 요구사항

1) 단일 연결 리스트가 주어졌을 때 리스트를 역순으로 정렬한다.

 

 

3. 핵심 아이디어

1) 연결 리스트 뒤집기 

 

연결 리스트는 한 방향으로만 연결되어 있다.

여기서 뒤집는다는 것은 각 노드가 가리키는 방향을 반대로 만든다는 뜻이다.

 

 

 

먼저 prev 포인터는 null로 초기화 하고, current 포인터는 head로 초기화한다.

prev는 이전 노드를, current는 현재 노드를 가리킨다.

 

current 포인터가 null 이 아닐 때 까지(연결 리스트의 끝에 도달할 때 까지)

current 노드의 next를 prev로 변경하여 방향을 반대로 바꾼다.

 

방향을 바꿨으니 다음 노드의 방향도 바꾸기 위해 

prev를 현재 노드로, current를 다음 노드로 이동한다.

 

모든 노드를 뒤집은 후, prev가 새로운 헤드가 되므로 이를 반환한다.

 

 

2) 코드

/**
 * Definition for singly-linked list.
 * class ListNode {
 *   int val;
 *   ListNode? next;
 *   ListNode([this.val = 0, this.next]);
 * }
 */
class ListNode {
  int val;
  ListNode? next;
  ListNode(this.val, [this.next]);
}

ListNode? reverseList(ListNode? head) {
  ListNode? prev = null;     // 처음엔 아무것도 가리키지 않음
  ListNode? current = head;     // 현재 노드는 head부터 시작

  while (current != null) {
    ListNode? nextTemp = current.next; // 다음 노드를 저장
    current.next = prev;               // 현재 노드의 방향을 반대로 바꿈
    prev = current;                    // prev를 현재 노드로 한 칸 옮김
    current = nextTemp;                // curr도 한 칸 앞으로 이동
  }

  // prev는 새로 바뀐 리스트의 첫 번째 노드
  return prev;
}

 

- 시간 복잡도 : O(n)

- 공간 복잡도 : O(1)