[LeetCode/EASY] 206. Reverse Linked List (JAVA) : 문제&풀이

 

 
연결리스트의 역을 구하는 문제이다.
ListNode를 매개변수로 받는 reverseList메서드의 틀이 주어진다.
 

Problem :

class Solution {
    public ListNode reverseList(ListNode head) {
        
    }
}

이 때, ListNode의 정의가 다음과 같이 주어진다.

public class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

풀이는 reverseList메서드에 작성하면 된다.

Solution :

재귀함수를 이용해 연결리스트의 역을 구하는 방법이다.

class Solution {
    public ListNode reverseList(ListNode head) {
        // 현재 노드 -> 가장 마지막 노드가 됨
        // 지금까지 역처리한 이전노드 없음(null)
        return reverse(head, null);
    }

    private ListNode reverse(ListNode curr, ListNode prev) {
        // 현재 노드가 null인 경우, 끝에 도달했으므로 이전 노드가 첫 노드가 됨
        if (curr == null) {
            return prev;
        }

        // 실제 다음 노드는 새로운 변수에 할당
        // 역 연결리스트의 이전 노드가 될 예정
        ListNode next = curr.next;
        // 실제 이전 노드는 역 연결리스트의 다음 노드로 설정
        curr.next = prev;

        // 다음 역전 대상은 실제 다음 노드와 현재 노드
        return reverse(next, curr);
    }
}

 

Example: