데이터 구조 면접 문제 요약 10 - 링크: 링크 종합

1940 단어 데이터 구조
질문 1: 링크 반전
문제 설명: 원본 링크 를 반전 시 킵 니 다.
Node* reverseList(Node *head)
{
    if (head == NULL)
    {
        return NULL;
    }
    Node *oldHead = head;
    Node *newHead = NULL;
    Node *temp = NULL;
    while(oldHead)
    {
        newHead = oldHead;
        oldHead = oldHead->next;
        newHead->next = temp;
        temp = newHead;
    }
    return newHead;
}

문제 2: 단일 체인 시트 의 마지막 k 번 째 요 소 를 찾 아 라.
분석: 두 개의 지침 을 사용 하 는데 이것 은 링크 문제 의 전형 적 인 방법 중 하나 인 앞 뒤 지침 이다.
Node* findReK(Node *head, int k)
{
    if (head == NULL)
    {
       return NULL;
    }
    Node *first = head;
    Node *second = head;
    int i = 0;
    while(first)
    {
        first = first->next;
        ++i;
        if (i > k-1)
        {
           second = second->next;
        }
    }
    return second;
}

문제 3: 싱글 체인 시트 중간 요 소 를 찾 아 라.
분석: 똑 같이 두 개의 지침 을 사용 하고 하나의 빠 른 지침 과 느 린 지침 을 사용 하 는데 이것 도 링크 문제 의 전형 적 인 해결 방법 중 하나 이다.
Node* findMid(Node* head)
{
    Node *p1, *p2;
    if (head == NULL || head->next == NULL)
    {
        return head;
    }
    p1 = p2 = head;
    while (1)
    {
        if (p2->next != NULL && p2->next->next != NULL)
        {
            p2 = p2->next->next;
            p1 = p1->next;
        }
        else
        {
            break;
        }
    }
    return p1;
}

질문 4: 헤더 없 는 링크 의 노드 삭제
분석: 삭제 의 가장 중요 한 점 은 바로 뒤의 노드 와 연결 하 는 것 입 니 다. 그러나 우 리 는 삭 제 된 앞의 노드 를 가 져 올 수 없습니다.그러나 삭 제 된 앞의 노드 의 next 는 삭 제 된 노드 의 메모리 주 소 를 가리 키 기 때문에 삭 제 된 노드 의 내용 을 삭 제 된 노드 의 메모리 에 복사 한 다음 에 삭 제 된 뒤의 노드 의 메모 리 를 삭제 합 니 다.
bool deleteNode(Node *node)
{
    if (node == NULL)
    {
        return false;
    }
    node->data = node->next->data;
    Node *temp = node->next;
    node->next = node->next->next;
    delete  temp;
    return true;
}

좋은 웹페이지 즐겨찾기