[LeetCode#92] Reverse Linked List II

❒ Description

---

제목	Reverse Linked List II
링크	https://leetcode.com/problems/reverse-linked-list-ii/
자료구조	선형 (연결 리스트)
시간복잡도	O(n)

이번 문제에서는 기억하고 있으면 나중에 사용하기 좋은 공식? 같은 것들을 알았다.

• 가상의 노드 Root 생성하기
• 특정 범위의 노드의 순서만 변경하기.

 
 
 

❒ Solution

---

public ListNode reverseBetween(ListNode head, int left, int right) {
    if (head == null) {
        return null;
    }
    // 가상의 노드 생성하기
    ListNode root = new ListNode(0);
    root.next = head;

    // 노드 변경 시작점으로 이동하기
    ListNode start = root;
    for (int i = 0; i < left - 1; i++) {
        start = start.next;
    }
    // 가장 가까운 변경 마지막 노드 설정하기
    ListNode end = start.next;

    // 해당 범위의 노드 순서 변경하기
    for (int i = 0; i < right - left; i++) {
        ListNode tmp = start.next;
        start.next = end.next;
        end.next = end.next.next;
        start.next.next = tmp;
    }
    return root.next;
}

 
이번 문제에서는 아래의 아이디어가 핵심으로 느껴진다.

• `left-1`로 변경해야 할 노드의 시작 점을 찾는다.
• `right - left` 로 변경해야 할 노드들만 타켓팅한다.
• 임시 변수를 활용하기.

---

그림을 통해 직관화

위 풀이를 이미지화

temp만 한 칸씩 앞으로 이동하고, start와 end는 각각 1과 2로 정되어 있다.