단 방향 링크 의 마지막 n 번 째 노드 삭제

제목: 함 수 를 써 서 단 방향 링크 의 마지막 n 번 째 노드 를 삭제 하 는 기능 을 완성 하고 삭 제 된 노드 포인터 (첫 번 째 노드 는 표 머리 이 며 삭 제 를 고려 하지 않 습 니 다) 를 되 돌려 줍 니 다.
struct SNode {     int value;     SNode *next; }; SNode rdel(SNode *head, int n);
 
1. 제목 을 leetcode 로 바 꾸 면 다음 과 같다.
링크 를 지정 하고 링크 의 마지막 n 번 째 노드 를 삭제 하 며 링크 의 머리 노드 를 되 돌려 줍 니 다.
본보기  링크 1 - > 2 - > 3 - > 4 - > 5 - > null 과 n = 2 를 드 립 니 다.
마지막 두 번 째 노드 를 삭제 하면 이 링크 는 1 - > 2 - > 3 - > 5 - > null 이 됩 니 다.
1) n 이 링크 길이 보다 큰 지 여 부 를 고려 하지 않 는 다.
생각:
두 바늘 을 정의 합 니 다. 처음에 이 두 바늘 의 next 지향 점 을 정의 한 다음 에 한 바늘 로 n 보 를 먼저 가게 한 다음 에 두 바늘 로 체인 시 계 를 동시에 옮 겨 다 녔 습 니 다. 첫 번 째 바늘 이 링크 의 끝 에 도 착 했 을 때 두 번 째 지침 은 삭제 할 마지막 n + 1 개의 매듭 점 을 가리 키 는 것 입 니 다. 

ListNode *rdel(ListNode* head, int n)
{
    ListNode l(0);
    ListNode *pre = &l;
    pre->next = head;
    ListNode *p = pre;
    ListNode *q = pre;
    
    for(int i = 0; i < n; i++)
    {
        p = p->next;
    }
    while(p->next != NULL)
    {
        p = p->next;
        q = q->next;
    }
    
    ListNode *k = q->next;//k         
    if(k == head)
    {
        head = head->next;
        return head;
    }
    q->next = k->next;    
    return head;

}

2) n 의 여러 가지 가능 한 상황 을 고려 할 때
생각:
두 개의 지침 을 정의 합 니 다. 처음에 각각 머리 결점 을 가리 키 고 한 개의 지침 을 n - 1 단계 먼저 가게 합 니 다. 이 어 두 개의 지침 이 동시에 링크 를 옮 겨 다 녔 습 니 다. 첫 번 째 지침 이 링크 의 끝 에 도 착 했 을 때 두 번 째 지침 은 삭제 할 마지막 n 번 째 결점 을 가리 키 는 것 입 니 다.  프로 그래 밍 에 주의해 야 할 것 은:
입력 한 링크 가 비어 있 거나 입력 한 n 이 합 법 적 이지 않 습 니 다.입력 한 n 은 링크 의 길이 보다 큽 니 다.삭제 해 야 할 노드 의 이전 노드 를 저장 해 야 합 니 다.삭 제 된 그 결점 은 두 결점 이다.

ListNode* removeNthFromEnd(ListNode* pHead, int n)
{
    ListNode* pFast = pHead;
    ListNode* pLow = pHead;
    ListNode* pPre = NULL;
    
    if (pHead == NULL || n <=0)
    {
        return NULL;//           n   
    }
    
    for (int i = 0; i < n-1; i++)
    {
        if(pFast->next != NULL)
        {
            pFast = pFast->next;
        }
        else
        {
            return NULL;//   n       
        }
    }
        
    while(pFast->next != NULL)
    {
        pFast = pFast->next;
        pPre = pLow;//                 
        pLow = pLow->next;
    }
    //  pLow           
    
    if (pLow == pHead)//           
    {
        pHead = pHead->next;
    }
    else
    {
        pPre->next = pPre->next->next;//    
    }
    return pHead;
}

테스트 코드:

struct ListNode
{
    ListNode(int x ): val(x), next(NULL){}
    int val;
    ListNode* next;
};

void BianLi(ListNode* pHead)
{
    ListNode* pCur = pHead;
    while(pCur!=NULL)
    {
        cout<val<next;
    }
}

void main()
{
    ListNode l1(1);
    ListNode l2(2);
    ListNode l3(3);
    ListNode l4(4);
    ListNode l5(5);
    ListNode l6(6);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = &l5;
    l5.next = &l6;
    l6.next = NULL;
    ListNode* pHead = &l1;

    BianLi(pHead);
    pHead = removeNthFromEnd(pHead, 2);
    cout<

결론: 만약 에 바늘 하 나 를 n 단계 로 먼저 가게 한다 면 첫 번 째 바늘 이 체인 테이블 의 끝 에 도 착 했 을 때 두 번 째 바늘 은 삭제 할 마지막 n + 1 개의 결점 을 가리킨다. 
            그리고 만약 에 바늘 하 나 를 먼저 n - 1 단계 로 가게 한다 면 첫 번 째 바늘 이 링크 의 끝 에 도 착 했 을 때 두 번 째 바늘 은 삭제 해 야 할 마지막 n 번 째 결점 을 가리 키 는 것 이다.
 
           프로그램의 건장 성 을 위해 서 는 다음 과 같은 고려 가 필요 하 다.
           1) 입력 한 링크 가 비어 있 거나 입력 한 n 이 합 법 적 이지 않 습 니 다.           2) 입력 한 n 은 링크 의 길이 보다 크다.           3) 삭제 해 야 할 결점 의 이전 결점 을 저장 해 야 한다.           4) 삭 제 된 그 결점 은 두 결점 이다.
참고:https://blog.csdn.net/u013108511/article/details/80404476 C + + 링크 조작 1: 마지막 n 번 째 노드 삭제
           https://blog.csdn.net/zwhlxl/article/details/47104535 [면접 문제] 링크 의 마지막 n 번 째 노드 를 삭제 합 니 다.