[java] Remove Nth Node From End of List

[참고문제] : https://leetcode.com/problems/remove-nth-node-from-end-of-list/

Remove Nth Node From End of List - LeetCode

문제 풀이

자체적인 자료구조를 제공하고 푸는 문제다.

자바는 Call By Value지만, 그 주소값(정확히는 주소를 가리키는 값)을 가지므로 마치 Call By Reference처럼 동작한다.

위 문장에 가끔 Deep Copy, Shallow Copy의 개념을 흔들 때가 있다.

 

생각의 흐름 - 일단 전체 길이부터 구하자.

전체 길이를 제공하지 않는다. 별도 함수를 만들어 Count를 먼저 알아보기로 했다.

 

생각의 흐름 - 마지막에서 N번째라면 Step이 어떻게 계산될 수 있을지 생각하자.

몇번이나 Next로 넘어가야 하는지를 알아야 한다.

전체 Count했으니, 거기서 N을 빼면 몇번째인지 알 수 있고,

Next값을 바꿔주면 될 것이다.

여기서 Head를 가지고 Next를 계산하면, 당연히 안된다.

그럼 Tmp변수에 Head를 할당시키면 문제 없을까?

내부 값을 변경시키는 거면, 당연히 문제가 된다. Tmp의 주소값이 결국 Head의 주소값이기 때문이다.

그렇지만, Tmp도 결국 변수기 때문에, Tmp에 Head.next를 대입시킨다는 개념이면 문제가 되지 않는다.

 

ListNode가 5개라고 가정하면,

ListNode 1

위와 같은 주소값(100~104)들을 가지는 Node가 5개 있다고 가정하자.

Head는 100이라는 주소값에 위치한다.

Tmp = Head라고 했을 때, Tmp도 Head와 동일한 주소값을 가진다.

그렇지만, Tmp = Tmp.next로 변화시키는 것은 Head에 영향을 주지 않는다. (tmp가 100에서 101을 보게 되는 것 뿐이며, Head는 여전히 100을 바라본다)

물론, Tmp.value 를 변경시키면 Head.value도 영향을 가지게 된다.

이 두가지를 적절히 혼합시켜야 한다.

ListNode 2

ListNode 3

Prev라는 변수를 만들어, Head와 동일 시 시킨다.

Tmp를 Next시키면서, Prev 변수에는 Next이전 값을 계속 가지게 한다.

그리고 Step이 마무리 되었을 때 (위의 경우 tmp가 3번의 Step을 넘어간 후 103번에 위치한 경우),

Prev.next = Tmp.next 로 동일하게 만들면, 102번의 next는 104번으로 변경이 된다.

결국 Head에서 next로 가다보면, 100 -> 101 -> 102 -> 104 로 변경되는 것이다.

 

생각의 흐름 - Step이 0이 나온다면?

움직이지 않는다가 아니라, 첫 시작이 바뀐다는 것을 캐치해야 했다.

Head를 Head.next로 대치해야 했다.

public ListNode removeNthFromEnd(ListNode head, int n) {
    int count = chkCount(head);
    ListNode tmp = head;
    ListNode prev = head;
    int step = count - n;
    if(step == 0) {
        head = head.next;
    } else {
        while(step > 0) {
            prev = tmp;
            tmp = tmp.next;
            step --;
        }
        prev.next = tmp.next;
    }
    return head;
}

public int chkCount(ListNode head) {
    ListNode tmp = head;
    int count = 1;
    while(tmp.next != null) {
        tmp = tmp.next;
        count ++;
    }
    return count;
}