[Algorithm] Dart로 풀어보는 역방향 연결 리스트 만들기

Reverse Linked List
Given the head of a singly linked list, reverse the list, and return the reversed list

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

Input: head = [1,2]
Output: [2,1]

Input: head = []
Output: []

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

 

Node란 연결 리스트(Linked List)에서 데이터를 저장하는 기본 단위

각 노드는 자신이 가진 데이터와 함께 다음 노드의 주소(포인터)도 함께 저장

 

 

예시 1번의 경우 아래와 같이 Node 리스트가 주어진다고 생각하면 됩니다.

ListNode head = ListNode(1, ListNode(2, ListNode(3, ListNode(4, ListNode(5)))));

 

 

[1, 2주소], [2, 3주소], [3, 4주소], [4, 5주소], [5, X]

위와 같은 형태라고 생각하시면 됩니다.

 

그리고 역순으로 했을때는 아래와 같이 바꿔주면 됩니다.

ListNode reversedHead = ListNode(5, ListNode(4, ListNode(3, ListNode(2, ListNode(1)))));

 

[5, 4주소], [4, 3주소], [3, 2주소], [2, 1주소], [1, X]

역순은 다음과 같은 형태라고 생각하시면 됩니다.

 

즉, [1]→[2]→[3]→[4]→[5]→null 형태를 반대의 형태 [5]→[4]→[3]→[2]→[1]→null 로 변경하도록 해야합니다.

 

 

일단, 쉬운 방법인 배열을 사용하는 방식으로 역방향으로 처리할 수 있습니다

List<ListNode> nodes = [];
ListNode? current = head;
while (current != null) {
  nodes.add(current);
  current = current.next;
}

for (int i = nodes.length - 1; i > 0; i--) {
  nodes[i].next = nodes[i - 1];
}
nodes[0].next = null;

 

넘겨받은 ListNode head 값을 List에 순차적으로 값을 넣고 [(1, 2주소), (2, 3주소), (3, 4주소), (4, 5주소), (5, X)] 리스트의 마지막 ListNode 의 next 값을 이전 값의 ListNode 값으로 변경해줍니다.

 

nodes[4].next = nodes[3]

nodes[3].next = nodes[2]

nodes[2].next = nodes[1]

nodes[1].next = nodes[0]

 

nodes[0].next = null

 

위와 같이 입력이 되면 기존에 주어진 ListNode 값을 역순으로 가지게 됩니다.

위와 같은 방식으로도 가능하나 위의 방식으로 했을 경우에는 for문을 2번 돌게 되고 추가로 List 를 사용하게 됩니다. 여기서 조금 더 효율적인 방법은 while 문을 통해서 작업을 해줄 수 있습니다.

 

ListNode? reverseList(ListNode? head) {
  if (head == null) return null;

  ListNode? prev;
  ListNode? current = head;
  
  while (current != null) {
    ListNode? next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

 

제일 처음 노드가 가리킬 다음 노드가 없는 마지막 노드 ListNode(5, X) 형태가 되어야합니다. 그래서 ListNode(1, ListNode(2)) 를 ListNode(1, X) 형태로 만들기 위해서 아무것도 가리키지 않는 null 을 prev 에 담아서 넣어주고 현재 ListNode(1) 을 prev 에 넣어서 다음 ListNode(2) 의 next 를 ListNode(1) 를 가리킬 수 있도록 해준다. 그리고 while 문은 반복문이기 때문에 다음 ListNode(2) 작업을 하도록 current 에 ListNode(2) 를 넣어준다. 이런 형태를 반복해서 작업하면 최후에 ListNode(5, null) 의 next 가 null 이기 때문에 최후에 current 값이 null 이 되어서 while 문을 벗어나게 됩니다.