leetcode 19 링크 의 마지막 N 번 째 노드 삭제

제목.
링크 를 지정 하고 링크 의 마지막 n 번 째 노드 를 삭제 하 며 링크 의 끝 점 을 되 돌려 줍 니 다.
예제: 하나의 링크 를 지정 합 니 다: 1 - > 2 - > 3 - > 4 - > 5, n = 2. 마지막 두 번 째 노드 를 삭제 한 후에 링크 는 1 - > 2 - > 3 - > 5 로 변 합 니 다.
설명: 주어진 n 보증 은 유효 합 니 다.
진급: 스 캔 을 한 번 사용 해 보 시 겠 습 니까?
문 제 를 풀다
전제: 단일 체인 시트 시퀀스 는 1 부터 시작 합 니 다.
해법 1: 두 번 의 순환 은 마지막 n 번 째 노드 를 삭제 해 야 한다. 그러면 우 리 는 마지막 n 번 째 노드 의 앞 노드, 즉 마지막 (n + 1) 번 째 노드 를 찾 아야 한다. 이 노드 의 next 를 n 번 째 노드 의 next 로 설정 하면 마지막 n 번 째 노드 를 삭제 하 는 작업 을 완성 할 수 있다.
단일 체인 표 에 pre 가 없 기 때문에 우 리 는 처음부터 옮 겨 다 닐 수 밖 에 없 기 때문에 '꼴찌 n 번 째 노드' 라 는 표현 방식 을 '순위 n 번 째 노드' 로 바 꿔 야 한다.
어떻게 변 할 까요?간단 합 니 다. 링크 의 길 이 는 len 이 고 마지막 n 번 째 노드 는 바로 순위 (len - n + 1) 입 니 다. 우리 가 실제 적 으로 찾 아야 할 것 은 그의 앞 노드, 즉 (len - n) 입 니 다.
링크 길 이 는 알 수 없 기 때문에 우 리 는 첫 번 째 순환 에서 링크 길이 len 을 찾 고 두 번 째 순환 에서 두 번 째 (len - n) 노드 를 찾 습 니 다.
순환 하기 전에 우 리 는 먼저 벙어리 노드 를 설정 하여 체인 헤더 에 연결 해 야 한다.왜 벙어리 노드 가 필요 합 니까?저 는 개인 적 으로 포 지 셔 닝 역할 을 하 는 것 으로 이해 합 니 다. 삭제 하려 는 링크 가 하나의 노드 만 있 으 면 삭제 한 후에 링크 로 돌아 갈 수 없 기 때 문 입 니 다.
해법 2: 한 번 에 한 번 순환 하려 면 두 개의 지침 (first, second) 이 필요 합 니 다. 그들 은 처음에 모두 벙어리 노드 를 가리 키 고 있 습 니 다.삭제 할 노드 가 마지막 n 번 째 라면 그 중의 한 지침 을 이동 하여 두 지침 사이 에 n 개의 노드 를 간격 으로 합 니 다 (예 를 들 어 마지막 두 번 째 지침 을 삭제 하려 면 first 와 second 가 2 개의 노드 를 간격 으로 합 니 다).
그리고 두 개의 바늘 을 동시에 움 직 여 다음 바늘 이 빈 노드 를 가리 킬 때 까지 합 니 다.
이렇게 하 는 목적 은 해법 1 에서 우리 가 두 번 순환 하 는 목적 은 '꼴찌 n 번 째 노드' 라 는 표현 방식 을 '순위 n 번 째 노드' 로 바 꾸 는 것 이다. 그러나 두 개의 지침 을 사용 하면 이 전환 이 필요 없다.두 바늘 이 '꼴찌 n 번 째 노드' 를 완벽 하 게 표현 할 수 있 기 때문이다.
다음 지침 은 '링크 끝 에서 부터' 두 지침 이 n 개의 노드 를 사이 에 두 고 'n 개의 노드' 를 나타 낸다. 앞의 지침 은 '제 (n - 1) 개의 노드' 를 나타 낸다.
그리고 우 리 는 이전 포인터 가 가리 키 는 노드 의 next 를 next. next 로 설정 하면 됩 니 다.

public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode dum = new ListNode(0);
            dum.next = head;
            ListNode first = dum;
            ListNode second = dum;

            while (n >= 0)
            {
                second = second.next;
                n--;
            }

            while (second != null)
            {
                first = first.next;
                second = second.next;
            }

            first.next = first.next.next;
            return dum.next;

참고:https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/solution/shan-chu-lian-biao-de-dao-shu-di-nge-jie-dian-by-l/