[문제15][LeetCode] 206. 역순 연결 리스트

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

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

 

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

 

접근 방법

1. 각 노드를 하나씩 방문하면서, 각 노드가 가리키는 다음 노드를 이전 노드로 바꾸면서 진행합니다.

각 단계에서 current의 next 포인터를 prev로 바꾸고, prev와 current를 한 노드씩 전진시킵니다. 이렇게 진행하면 모든 노드를 처리한 후에는 prev가 새로운 리스트의 헤드가 됩니다.

2. 시간복잡도 : O(N)

각 노드를 한 번씩만 방문하므로 길이에 비례합니다.

 

코드 구현

성공 코드

/**
 * 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; }
 * }
 */
public class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;  
        ListNode current = head;  

        // 리스트의 끝까지 반복
        while (current != null) {
            ListNode next = current.next;  
            current.next = prev;  // 현재 노드의 다음을 이전 노드로 설정 (역방향)
            prev = current;  // 이전 노드를 현재 노드로 이동
            current = next;  // 현재 노드를 다음 노드로 이동
        }

        // 마지막엔 prev가 새로운 헤드가 됨
        return prev;
    }
}

코드 최적화 뿌-듯

 

배우게 된 점

1. return prev; 한 이유

노드들을 하나씩 처리하면서, 각 노드의 next 포인터를 prev로 변경합니다. 이렇게 current == null이 될 때 까지 진행하게 되면  노드의 방향이 반대로 바뀌는 새로운 리스트가 탄생하는데, prev는 새로운 리스트의 head가 됩니다.