206. Reverse Linked List

단일 연결 목록의 헤드가 주어지면 목록을 뒤집고 반전된 목록을 반환

연결 리스트의 이전노드, 현재노드, 다음노드의 포인터를 반전시키면서 마지막 노드까지 처리한다.

Recursive

class Solution {
    // T: O(n)
    // S: O(n)
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }

        // 뒤에서부터 꺼꾸로 작업한다.
        ListNode p = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return p;
    }
}

Iterative

/**
 * 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 {
    // 현재노드, 이전노드, 다음노드를 이동하면서 마지막 노드까지 진행한다.
    // T: O(n)
    // S: O(1)
    public ListNode reverseList(ListNode head) {
        ListNode node = head;
        ListNode prev = null;
        ListNode next = null;
        
        while (node != null) {
            // 다음노드를 저장하고
            next = node.next;
            // 현재노드의 포인터를 이전노드로 만들고
            node.next = prev;
            // 이전노드는 현재노드로
            prev = node;
            // 현재노드는 다음노드로 진행한다.
            node = next;
        }
        
        // 마지막 노드(이전노드)가 헤드가 된다.
        return prev;
    }
}

Share this post