[자바 알고리즘 인터뷰] 8장 연결 리스트(7) - 역순 연결리스트 2

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

 

- 위치 left에서 right까지를 역순으로 만들어라. 위치는 1부터 시작한다. 

 

 

풀이 1) 반복 구조로 노드 뒤집기 

 

- 우선 변경이 필요한 위치의 바로 앞까지 다음과 같이 이동 

//임시 노드 선언
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;

 

- start는 변경이 필요한 2의 바로 앞 지점 1을 가리키고, end는 start.next인 2를 가리킨다. 

- head는 1인데, 그보다도 더 앞에 root를 만들어 head보다 이전에 위치시킨다. 

- 나중에는 root.next를 최종 결과로 리턴하게 된다. 

 

- 이렇게 할당된 start와 end는 끝까지 값이 변하지 않는다. 즉, 1과 2의 값이 마지막까지 유지되며, start와 end를 기준으로 반복하면서 역순으로 뒤집음

 

출처: 자바 알고리즘 인터뷰 with 코틀린 저자: 박상길 <책만>

 

- start.next를 tmp로 지정하고 start.next는 end.next가 된다. 

- 그리고 end.next는 end.next.next로 한 칸 더 앞의 값을 가리킨다. 

- 그리고 start.next.next를 tmp로 지정한다. 

- 이 같은 구조로 right-left만큼 반복한다. 

//right-left만큼 위치 변경 진행
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;
}

 

 

class 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;

        //right-left만큼 위치 변경 진행
        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;

    }
}