leetcode 92. Reverse Linked List II

 

 

start 지점까지 가서 뭔가를 저장하고있다가 뒤집어야겠다는 생각을 했었는데,

그러면 시간이 너무오래걸릴것같았다.

 

책의 풀이를 참고해보니 일단 start 지점까지 가는것으로 시작하였다.

 

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
    if (head == null) return head;
    
    ListNode root = new ListNode(0);
    root.next = head;
    
    ListNode start = head;
    
    if (int i=0; i<left-1; i++ {
    	start=start.next;
    }
    
    }
}

 

우선 null 예외처리를 해주고

 

이리저리 손질보고나서 리턴을 예쁘게 하기위해 root 라는 새로운 ListNode 를 만들어주고 head 를 연결했다.

나중에 리턴할때는 root.next로 리턴할것이다.

 

앞으로 보낼 ListNode start 를 하나 만들고 left 파라미터 만큼 이동하기로했다.

주어진숫자는 자릿수이기때문에 index에 맞추려고 -1 해줌.

 

그리고 어떤식으로 살펴갈까 생각을 했는데

 

앞에 있는걸 뒤로 옮기자니 도루묵이 되어버렸고

start 지점을 기억하고 뒤에서 ++ 한 자릿수만큼 이동한뒤 끌어와야겠다고 생각했다.

 

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
    
    if (head == null) return head;
    
    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 따로저장
        start.next = end.next; //start next.next를 next로 땡겨옴
        end.next = end.next.next; //end의 자릿수를 뒤로 이동 
        start.next.next = tmp; //다시 원래의 next를 저장
    }
    return root.next;
    
    }
}

 

end 를 만들어주고 loof를 돌렸다.

 

첫번째 loop

head = 1 2 3 4 5 6

start =  1 2 3 4 5 6

end = 2 3 4 5 6

ListNode tmp = start.next;
start.next = end.next;

 

tmp = 2 3 4 5 6

start = 1  + 3 4 5 6

start 의 next 가 end 의 next로 당겨졌다.

 

start 는 head 이므로, head 도 변하였다.

head = 1 3 4 5 6

end.next = end.next.next;
start.next.next = tmp;

 

 

end = 2 4 5 6 

 

end 의 next가 next.next로 당겨지고 이때 tmp 도 3이 빠진 2 4 5 6 으로 변하는 것으로..이해했다..

 

start.next.next = tmp 를 통해서 start = 1 3 2 4 5 6

 

두번째 loop

루프돌기전에

start = 1 3 2 4 5 6

end = 2 4 5 6

ListNode tmp = start.next;
start.next = end.next;

tmp = 3 2 4 5 6

 

start = 1 + 4 5 6

end.next = end.next.next;
start.next.next = tmp;

 

end = 2 5 6

이때tmp도 3 2 5 6

 

start = 1 4 3 2 5 6

 

..

이런식으로 바꿔나가면 된다!