LeetCode - 206 역방향 연결리스트

206. 역방향 연결리스트

 

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

 

문제

단일 연결 리스트의 헤드가 주어졌을 때, 리스트를 역순으로 뒤집으세요.

 

풀이

1. 이전 노드, 현재 노드를 초기화한다.

2. 현재 노드가 null 이 될 때까지 반복문 진행

3. 현재 노드의 다음 노드를 nextTemp 에 임시 저장

4. 현재 노드의 다음 노드를 이전 노드로 변경

5. 이전 노드를 현재 노드로 변경

6. 현재 노드를 다음 노드로 이동

7. 다음으로 계속 이동한 prev 는 제일 뒤에 있는 노드

class Solution {
  ListNode? reverseList(ListNode? head) {
    ListNode? prev = null;
    ListNode? current = head;

    while (current != null) {
      ListNode? nextTemp = current.next; // 현재 노드의 다음 노드를 temp 에 임시 저장
      current.next = prev; // 현재 노드의 다음 노드를 이전(prev) 노드로 변경
      prev = current; // 이전 노드를 현재 노드로 변경
      current = nextTemp; // 현재 노드를 다음 노드로 이동
    }
    return prev;
  }
}

class ListNode {
  int val;
  ListNode? next;
  ListNode([this.val = 0, this.next]);
}

 

이해가 잘 안되니 그림으로 살펴보자

ListNode 는 아래 그림과 같이 val 값과 다음 노드를 바라보는 next 포인터가 있는 자료구조이다.

 

reverseList 메서드가 호출되면 반복문 이전에서 초기화한 값은 아래의 그림과 같다.

---

첫번째 반복문

current.next = prev 라인으로 인해 ListNode(1) 의 next 포인터는 null 로 바뀐다.

prev 는 ListNode(1), current 는 ListNode(2) 로 바뀐다.

첫번째 반복문 이후의 prev 와 current 값

---

두번째 반복문

current.next = prev 라인으로 인해 ListNode(2) 의 next 포인터는 ListNode(1) 로 바뀐다.

prev 는 ListNode(2), current 는 ListNode(3) 로 바뀐다.

 

---

세번째 반복문

current.next = prev 라인으로 인해 ListNode(3) 의 next 포인터는 ListNode(2) 로 바뀐다.

prev 는 ListNode(3), current 는 ListNode(4) 로 바뀐다.

---

네번째 반복문

current.next = prev 라인으로 인해 ListNode(4) 의 next 포인터는 ListNode(3) 로 바뀐다.

prev 는 ListNode(4), current 는 ListNode(5) 로 바뀐다.

---

다섯번째 반복문

current.next = prev 라인으로 인해 ListNode(5) 의 next 포인터는 ListNode(4) 로 바뀐다.

prev 는 ListNode(4), current 는 null 로 바뀐다.

다섯번째 반복문에서 current 값이 null 이 되므로 반복문을 빠져나오고 prev 값을 리턴한다.

1->2->3->4->5 순서였던 연결 리스트가

5->4->3->2->1 순서로 변경된다.