LeetCode - 206 역방향 연결리스트

기타/알고리즘

LeetCode - 206 역방향 연결리스트

개발짜 2024. 11. 6. 15:52

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]);
}