[Java, Python] Leetcode - 206. Reversed Linked List

문제

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

간단하게 연결리스트가 주어지면 뒤집어서 반환하는 문제입니다.

풀이

1. 초기화
   • node는 현재 연결 리스트의 첫 번째 노드를 가리키고, prev는 None으로 설정됩니다. prev는 결국 역순으로 뒤집힌 리스트의 새로운 첫 번째 노드를 가리키게 될 것입니다.
2. 반복문
   • node가 None이 아닐 때까지 반복합니다. 즉, 리스트의 끝에 도달할 때까지 반복됩니다.
   • 먼저, 현재 노드의 다음 노드를 next에 저장합니다. 이는 역순으로 리스트를 뒤집기 전에 원래의 리스트 구조를 기억하기 위함입니다.
   • 그 다음, 현재 노드의 next 포인터를 이전 노드 (prev)로 변경하여 리스트를 역순으로 연결하기 시작합니다.
   • prev를 현재 노드로 이동시키고, node를 다음 노드로 이동시킵니다.
3. 반환
   • 반복문이 끝나면, prev는 역순으로 뒤집힌 리스트의 새로운 head(첫 번째 노드)를 가리키고, 이 값을 반환합니다.

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        node, prev = head, None

        while node:
            # node.next를 이전 prev 리스트로 계속 연결하면서 끝날 때까지 반복
            next, node.next = node.next, prev
            prev, node = node, next

        return prev

 

Java

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode prev = null;
        ListNode node = head;
        
        while (node != null) {
            // 다음 노드를 저장
            ListNode next = node.next;
            // 현재 노드의 다음을 이전 노드를 가리키도록 변경
            node.next = prev;
            // prev와 node를 한 단계 앞으로 이동
            prev = node;
            node = next;
        }
        
        // 역순으로 뒤집힌 리스트의 새로운 head 반환
        return prev;
    }
}

 

재귀 호출을 사용하는 방법으로도 해결할 수 있습니다. 노드가 없거나 마지막 노드일 때 까지 반복하여 반전하는 방법입니다. 코드가 더 직관적이긴 하지만 시간 복잡도 측면에서 조금 더 비효율적입니다.

Python

class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if (head == None or head.next == None):
            return head
        newHead = self.reverseList(head.next)
        head.next.next= head
        head.next = None

        return newHead

JAVA

class Solution {
    public ListNode reverseList(ListNode head) {
        // 재귀 종료 조건: 노드가 없거나 마지막 노드인 경우
        if (head == null || head.next == null) {
            return head;
        }
        
        // 나머지 리스트를 재귀적으로 반전
        ListNode newHead = reverseList(head.next);
        
        // 현재 노드 다음의 노드가 현재 노드를 가리키도록 설정
        head.next.next = head;
        head.next = null;  // 현재 노드의 next를 null로 설정
        
        return newHead;
    }
}