[Java] leetcode 92. Reverse Linked List II

구현한 코드이다.

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null) {
            return null;
        }
        if (left == right) {
            return head;
        }

        ListNode cur = head;
        ListNode prev = new ListNode();
        prev.next = head;
        for (int i = 0; i < left - 1; i++) {
            prev = cur;
            cur = cur.next;
        }
        for (int i = 0; i < right - left; i++) {
            ListNode next = cur.next;
            cur.next = next.next;
            next.next = prev.next;
            prev.next = next;
        }
        if (left == 1) {
            return prev.next;
        } else {
            return head;
        }
    }
}

 

방법은 의외로 간단하다. left 에서 right까지 이동하는 동안, 만났던 노드들을 left의 왼쪽으로 이동시켜주면 자연스럽게 reserver가 된다.

[1,2,3,4,5] lisNode가 있고 left 가 2이고, right 4 인 상황을 살펴보자.
한번만 listNode를 순회하여 reverse를 시킬 것이다.
먼저 left 의 왼쪽에 있는 node까지이동하고, left의 왼쪽 node 를 prev 라고 한다.

1 -> 2 -> 3 -> 4 -> 5
^    ^    ^
|    |    |
prev cur  next

cur node는 left 에 위치한 node이고, cur.next 가 next node 가 된다.
cur.next = next.next;
next.next = prev.next;
prev.next = next;
로 하게 되면 아래와 같이 변한다. next node를 prev.next 로 끼워 넣는 것이다.

1 -> 3 -> 2 -> 4 -> 5
^    ^    ^
|    |    |
prev next cur

next를 다시 설정하여, 아래와 같이 설정한다.

1 -> 3 -> 2 -> 4 -> 5
^         ^    ^
|         |    |
prev      cur next

그 다음 다시 next node를 prev.next로 설정한다.

1 -> 4 -> 3 -> 2 -> 5
^    ^         ^   
|    |         |    
prev next      cur

이 과정을 계속 반복하면 된다.