커 리 어 컵 - 링크 2.3

2.3 하나의 알고리즘 을 실현 하고 단 방향 링크 중간의 특정한 노드 를 삭제 하 며 이 노드 에 만 접근 할 수 있다 고 가정 합 니 다.(즉, 너 는 머리 결 점 을 모른다)
이 문제 의 관건 은 결점 을 삭제 하 는 지침 이 하나 밖 에 없다 는 것 이다. 만약 그것 을 직접 삭제 하면 이 링크 는 끊 어 질 것 이다.그러나 당신 은 이 결점 이 생기 기 전에 점 을 찍 는 지침 을 얻 을 수 없습니다. 그렇습니다. 그것 은 머리 결점 도 제공 하지 않 습 니 다.이런 상황 하에 서 너 는 다른 길 을 찾 을 수 밖 에 없다.이 문 제 를 다시 한 번 살 펴 보면 우 리 는 c 결점 에서 시작 한 후의 지침 만 얻 을 수 있 습 니 다. 만약 당신 이 c 결점 후의 어떤 결점 을 삭제 하 라 고 한다 면 틀림없이 문제 가 없 을 것 입 니 다.예 를 들 어 결점 d 를 삭제 하면 c 의 next 지침 을 e 로 가리 키 고 delete d 는 ok 입 니 다.좋 습 니 다. 만약 에 우리 가 결점 d 를 삭제 하면 우 리 는 a - > b - > c - > e 를 얻 을 수 있 습 니 다. 목표 링크 와 하나의 결점 만 차이 가 납 니 다.어 떡 하지?d 의 데 이 터 를 c!결점 구 조 는 모두 같 습 니 다. 누구나 똑 같 습 니 다. 가장 중요 한 것 은 결점 중의 데 이 터 를 삭제 하 는 것 입 니 다. 우리 가 남 긴 것 이 데이터 a - > b - > d - > e 만 있 으 면 됩 니 다.
아이디어 가 생 겼 어 요. 코드 를 직접 쓰 시 겠 어 요?등등, 코드 를 쓰기 전에 발생 할 수 있 는 여러 가지 상황 을 간단하게 분석 합 시다 (물론 경계 상황 포함).만약 c 가 링크 를 가리 키 는: 1. 머리 결점;2. 중간 결산 점.3. 끝 점.4. 비어 있다.상황 1, 2 는 정상 적 인 상황 에 속 하고 d 의 데 이 터 를 c, c 의 next 포인터 가 d 의 next 가 가리 키 는 결점 을 가리 키 며 d 를 삭제 하면 OK 입 니 다.상황 4 가 비어 있 으 면 바로 돌아 갑 니 다.상황 3 은 비교적 특수 하 다. 만약 에 c 가 꼬리 결점 을 가리 키 면 보통 c 를 직접 삭제 하면 된다 고 생각 할 것 이다. 어차피 c 뒤에 도 결점 이 없 으 니 체인 시계 가 끊 어 질 까 봐 걱정 하지 않 아 도 된다.그런데 정말 그런 가요?코드 는 c 를 직접 삭제 하고 c 를 가리 키 는 결점 (예 를 들 어 b) 의 next 지침 이 비어 있 지 않다 는 것 을 알려 줍 니 다.즉, 만약 당신 이 이 링크 를 인쇄 한다 면, 그것 은 원래 링크 의 길이 와 같은 링크 를 인쇄 할 것 입 니 다. 그리고 마지막 요 소 는 0 입 니 다!
 

     ，  CTCI      ，             。  ，           ，   c     ，              ，              。              ，             。  ，          。

C + + 구현 코드:

#include<iostream>

#include<new>

using namespace std;



struct ListNode

{

    int val;

    ListNode *next;

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

};



void createList(ListNode *&L)

{

    int arr[10]= {1,2,3,2,5,6,7,3,9,1};

    int i;

    ListNode *p=NULL;

    for(i=0; i<10; i++)

    {

        ListNode *tmp=new ListNode(arr[i]);

        if(L==NULL)

        {

            L=tmp;

            p=tmp;

        }

        else

        {

            p->next=tmp;

            p=tmp;

        }

    }

}



void deleteNode(ListNode *c)

{

    if(c==NULL||c->next==NULL)

        return;

    ListNode *d=c->next;

    c->next=d->next;

    c->val=d->val;

    d->next=NULL;

    delete(d);

}



int main()

{

    ListNode *head=NULL;

    createList(head);

    ListNode *p=head;

    while(p)

    {

        cout<<p->val<<" ";

        p=p->next;

    }

    cout<<endl;

    deleteNode(head->next->next->next);

    p=head;

        while(p)

    {

        cout<<p->val<<" ";

        p=p->next;

    }

    cout<<endl;

}