Linked List | Reverse Linked List II

Given the head of a singly linked list and two integers left and right where left <= right, reverse the nodes of the list from position left to position right, and return the reversed list.

 

Example 1:

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

Example 2:

Input: head = [5], left = 1, right = 1
Output: [5]

 

Constraints:

• The number of nodes in the list is n.
• 1 <= n <= 500
• -500 <= Node.val <= 500
• 1 <= left <= right <= n

 

Reverse Linked List 문제에서 조금더 심화된 문제이다. 노드가 500개까지 만들어질 수 있고, 값은 -500에서 500까지 존재한다. Linked List에서 어느 부분이라도 중간 또는 전체를 Reverse하라는 문제이다. 이 문제에서 포인트는, 중간만 바꾸어야한다는 점이다. 아래와같이 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; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if(head == null) return null;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = moveN(dummy, left - 1);
        
        ListNode curr = prev.next;
        ListNode nextNode = curr.next;
        
        for(int i = 0; i < right - left; i++){
            curr.next = nextNode.next;
            nextNode.next = prev.next;
            prev.next = nextNode;
            nextNode = curr.next;
        }
        
        return dummy.next;
    }
    
    private ListNode moveN(ListNode node, int n){
        while(n > 0){
            node = node.next;
            n--;
        }
        return node;
    }
}

moveN 이라는 helper method를 만들었는데, 이것은 따로 만들지 않아도 된다. 하지만, 재사용 가능한 function이라고 생각해서 private 함수로 작성했다. reverse를 해야하는 노드들중 가장 오른쪽 노드의 전 노드까지 가서, 1, 3이라고 한다면 2회를 뒤집어야하기 때문에 right - left만큼 for loop을 이용해서 하나씩 차례차례 뒤집어주었다. 단, reverse에 해당하지 않는 마지막 왼쪽 사이드의 노드의 위치를 기억해두고, 마지막으로 뒤집혀서 첫번째 순서가 된 노드를 가르키도록 했다. 또한 dummy node를 사용해서, head를 쉽게 리턴할 수 있도록 했다.

 

Time Complexity: O(N)

Space Complexity: O(1)

 

이 모든것은, 전체 노드를 loop 하기때문에 O(N)으로 처리할 수 있고, space 또한 포인터로 사용하고, dummy node를 생성하는 듯, 숫자로 셀 수 있는 만큼만 사용하기 때문에 O(1)이다.

 

100%의 최상위 속도로 풀 수 있었다.

 

위 포켓몬들에서 2번째에서 4번째자리에 있는 포켓몬을 거꾸로 세워주세요~

 

Reference

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

Reverse Linked List II - LeetCode