[LeetCode] 206. Reverse Linked List - Java

https://leetcode.com/problems/reverse-linked-list/description/

Reverse Linked List - LeetCode

---

문제

Given the head of a singly linked list, reverse the list, and return the reversed list.

 

Example 1:

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

Example 2:

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

Example 3:

Input: head = []
Output: []

 

Constraints:

• The number of nodes in the list is the range [0, 5000].
• -5000 <= Node.val <= 5000

 

Follow up: A linked list can be reversed either iteratively or recursively. Could you implement both?

---

풀이

풀이 과정

주어진 Linked List 를 역순으로 뒤집는 문제이다.
함수를 재귀호출하여 뒤에서 부터 next가 가리키는 값을 바꾸어 주도록 한다.

빈 리스트이거나 다음 노드가 없는 경우 재귀 호출을 종료하고 아닌 경우 다음 노드를 호출한다/

// 빈 리스트이거나 다음 노드가 없으면 재귀 호출 종료
if(head == null || head.next == null){
    return head;
}

// 다음 노드 재귀 호출
ListNode List = reverseList(head.next);

 

현재 탐색중인 노드의 다음 노드가 가리킬 next 값을 현재 노드의 head 값으로 설정하고 현재 노드가 가리키는 next 값은 null로 설정하여 연결을 끊어준다.

// 현재 노드의 다음 노드가 가리키는 next 값을 현재 head로 설정
head.next.next = head;
// 현재 노드가 가리키는 다음 노드를 null로 설정
head.next = null;

 

재귀 호출이 완료되어 최종 변경된 리스트를 반환한다.

// 변경된 List를 return
return List;

---

최종 코드

/**
 * Definition for singly-linked list.
 * 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; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        // 빈 리스트이거나 다음 노드가 없으면 재귀 호출 종료
        if(head == null || head.next == null){
            return head;
        }

        // 다음 노드 재귀 호출
        ListNode List = reverseList(head.next);

        // 현재 노드의 다음 노드가 가리키는 next 값을 현재 head로 설정
        head.next.next = head;
        // 현재 노드가 가리키는 다음 노드를 null로 설정
        head.next = null;

        // 변경된 List를 return
        return List;
    }
}

---