92. Reverse Linked List II

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

Reverse Linked List II - LeetCode

 

1. 문제와 예제, 그리고 제약사항

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

 

2. 문제 풀이

 

문제 해석은 단순하게 left와 right값이 주어지고 노드로 구성된 Linked List에서 left와 right의 값을 변경하면 된다.

 

이 문제는 Linked List에서 다음 객체 주소 값을 가지고 있다는 점을 활용하여 풀면 되고  소스 및 풀이는 LeetCode에 공개된 hi-malik의 소스 코드를 통해 풀이해본다.

(https://leetcode.com/problems/reverse-linked-list-ii/discuss/2311084/JavaC%2B%2B-Tried-to-Explain-every-step)

 

먼저  소스 코드는  다음과 같다.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0); // created dummy node
        dummy.next = head;
        ListNode prev = dummy; // intialising prev pointer on dummy node
        
        for(int i = 0; i < left - 1; i++)
            prev = prev.next; // adjusting the prev pointer on it's actual index
        
        ListNode curr = prev.next; // curr pointer will be just after prev
        // reversing
        for(int i = 0; i < right - left; i++){
            ListNode forw = curr.next; // forw pointer will be after curr
            curr.next = forw.next;
            forw.next = prev.next;
            prev.next = forw;
        }
        return dummy.next;
    }
}

Linked LIst의 이동을 위해서 prev, curr, forw 3개의 Linked List를 활용하였다.

forw는 변경해야할 노드를 처음 순서로 가지고 있는 Linked List 이고 curr은 순서를 변경할 노드를 포함하고 순서를 변경 후에  변경 시킨 노드 이후의 값을 가지고 있는 Linked List이다. prev는 순서 이동이 완료된 후 전체 Linked List의 모습이다.

 

이제 소스 코드를 통해 노드들의 변화를 알아보자.

 

 

  2가 오른쪽으로 이동된 후 아직 right자리에 가지 않았깅에 위의 과정을 다시 한번 수행한다.

과정이 종료되고 나면 2번째  자리에는 기존 4번째 값이었던 4가, 4번째 자리에는 2가 오게 된다.