알고리즘 - 링크 의 간단 한 알고리즘 문제 (계속)

한 편 이면 다 쓸 수 있 을 줄 알 았 는데 한 편 이 더 많아 진 것 같 아서 링크 에 관 한 간단 한 알고리즘 문제 에 속편 이 추가 되 었 습 니 다. 전편 과 마찬가지 로 어렵 지 않 습 니 다.

링크 에서 꼴찌 k 번 째 노드

두 개의 순 서 를 합 친 링크

두 개의 링크 중의 첫 번 째 공공 노드

를 찾 았 다.
1. 링크 의 마지막 k 번 째 노드
문제 설명: 링크 를 입력 하여 링크 의 마지막 k 번 째 노드 를 계산 합 니 다 (1 부터 계산 합 니 다).
알고리즘 사상
우 리 는 체인 테이블 의 결점 개수 n 과 꼴찌 k 의 결점 간 의 관 계 를 분석 할 수 있다. 만약 에 체인 테이블 에 n 개의 결점 이 있다 면 그의 꼴찌 k 의 결점, 즉 체인 테이블 이 수 를 따라 가 는 n - k + 1 의 결점 이다.사고 1: 먼저 링크 를 옮 겨 다 니 며 노드 의 개수 n 을 얻 은 다음 에 링크 를 옮 겨 다 니 며 n - k + 1 개의 노드 를 찾 습 니 다.이 사고방식 은 체인 시 계 를 두 번 옮 겨 다 녀 야 하 는데 시간 복잡 도 는 O (n) 이다.사고방식 2: 한 번 에 옮 겨 다 니 면 결점 을 찾 을 수 있 을까요?이것 이 바로 다음 에 할 말 이다.우 리 는 두 개의 지침 을 사용 할 수 있 습 니 다. 첫 번 째 지침 은 처음부터 시작 하여 k - 1 보 를 앞으로 간 다음 에 두 번 째 지침 은 첫 번 째 결점 을 가리 키 고 그 다음 에 두 개의 지침 순 서 를 뒤로 이동 할 수 있 습 니 다. 첫 번 째 지침 이 마지막 결점 을 가리 킬 때 두 번 째 지침 은 마침 마지막 k 개의 몇 시 를 가리 키 고 있 습 니 다.두 바늘 사이 의 간격 은 k - 1 이다.
코드:
알고리즘 사상 이 명확 해진 후에 코드 는 훨씬 간단 해 졌 다.코드 를 쓴 후에 우 리 는 노 봉 성 을 주목 하고 특수 한 입력 에 대해 코드 가 임 무 를 완성 할 수 있 는 지 를 주목 해 야 한다.이것들 은 모두 코드 에서 고려 해 야 할 것 이다.특수 입력: 1. pHead 가 NULL 이면 마지막 K 번 째 노드 가 존재 하지 않 으 므 로 NULL 로 돌아 가 야 합 니 다.2. k 가 받 은 부호 가 없 는 숫자 입 니 다. k = 0 을 입력 하면 k 는 부호 가 없 기 때문에 for 가 k - 1 회 순환 할 때 얻 는 것 은 - 1 이 아니 라 매우 큰 숫자 입 니 다. for 순환 의 횟수 는 우리 가 예상 한 것 을 초과 할 것 입 니 다.3. 입력 한 k 가 링크 의 노드 총수 보다 크 면 for 순환 으로 링크 를 옮 겨 다 닐 때 NULL 을 가리 키 는 지침 이 나타 납 니 다.
링크 의 데이터 구조 정의:

typedef struct ListNode *list_pointer;
typedef struct ListNode
{
    int value;
    list_pointer link;
};
list_pointer pHead;

링크 의 마지막 k 번 째 노드 를 찾 습 니 다 (1 부터 계산 합 니 다).

list_pointer FindKthNodeFromEnd(list_pointer pHead, unsigned int k)
{
    //         1  ，        0   
    if (pHead == NULL || k == 0) {
        return NULL;
    }
    list_pointer pAhead = pHead;
    list_pointer pBehind;

    for (int i = 0; i < k - 1; i++)
    {
        if (pAhead->link)//  k             
        {
            pAhead = pAhead->link;
        }
        else
        {
            fprintf(stderr, "K is bigger than length of linklist
");
            exit(1);
        }
    }

    pBehind = pHead;
    while (pAhead->link)//  pAhead           
    {
        pAhead = pAhead->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

관련 제목
비슷 한 문제 가 아직 많 으 니 우 리 는 두 개의 지침 을 빌려 빠르게 결 과 를 얻 을 수 있다.제목 1: 링크 의 중간 결산 점 을 구하 고 링크 의 결산 포인트 가 홀수 라면 중간 결산 점 을 출력 합 니 다. 만약 에 링크 의 결산 포인트 가 짝수 라면 중간 두 개 중 하 나 를 출력 합 니 다.알고리즘 사상: 두 개의 지침 을 정의 합 니 다. 한 지침 은 한 번 에 한 걸음 씩 가 고 다른 지침 은 한 번 에 두 걸음 씩 갑 니 다. 빠 른 지침 이 링크 의 끝 에 도착 하면 느 린 것 이 링크 의 중간 결점 을 가리 키 는 것 입 니 다.제목 2: 단 방향 링크 가 링 링크 인지 아 닌 지 판단 합 니 다.알고리즘 사상: 두 개의 지침 을 정의 합 니 다. 첫 번 째 노드 부터 한 개의 지침 이 한 번 에 한 걸음 씩 걷 고 다른 지침 이 한 번 에 두 걸음 씩 걷 습 니 다. 만약 에 빠 른 지침 이 느 린 지침 을 쫓 으 면 이 체인 시 계 는 링 입 니 다. 만약 에 빠 른 지침 이 링크 의 끝 에 이 르 러 느 린 지침 을 쫓 지 못 하면 링 체인 시계 가 아 닙 니 다.
코드
여기에 제목 1 의 코드 를 썼 으 니 참고 하 세 요.주의해 야 할 코드 중의 while 의 순환 조건 은 pAhead 와 pAhead - > link 를 판단 하 였 습 니 다. 여 기 는 끝 노드 를 가리 키 는 지 여 부 를 판단 하 는 것 입 니 다. 만약 에 링크 의 결 점 이 짝수 라면 pAhead = = NULL 로 끝 노드 에 도착 하 는 지 여 부 를 판단 합 니 다.링크 에 홀수 의 결점 이 있다 면 pAhead - > link = = NULL 로 판단 합 니 다.

//     
list_pointer getTheMiddleNode(list_pointer pHead)
{
    if (pHead == NULL){
        fprintf(stderr, "the linklist is empty.
" );
        exit(1);
    }
    if (pHead->link == NULL)//           ，           
        return pHead;
    list_pointer pAhead = pHead, pBehind = pHead;
    //               
    while (pAhead && pAhead->link)
    {
        pAhead = pAhead->link->link;
        pBehind = pBehind->link;
    }
    return pBehind;
}

2. 정렬 된 링크 두 개 를 합 칩 니 다.
문제 설명: 두 개의 정렬 된 링크 를 입력 하고 두 개의 링크 를 합 친 다음 에 합 친 링크 의 끝 점 을 되 돌려 줍 니 다.
알고리즘 사상
두 개의 바늘 로 하 나 는 a 링크 의 결산 점 을 가리 키 고 하 나 는 b 링크 의 결산 점 을 가리킨다.모두 체인 헤드 부터 차례대로 비교 합 니 다.두 개의 링크 중의 첫 번 째 노드 에 대해 크기 를 비교 하고 작은 노드 를 합 친 후의 링크 에 추가 한 다음 에 링크 를 합 친 그 링크 지침 을 넣 고 이동 한 다음 에 노드 를 절약 하 는 두 노드 를 계산 한 다음 에 계 산 된 노드 를 링크 의 링크 꼬리 에 연결 시 키 고 나머지 노드 도 이렇게 처리한다.이렇게 분석 해 보면 전형 적 인 귀속 이다.재 귀 를 사용 하면 우 리 는 이 문 제 를 빨리 해결 할 수 있다.
코드

//          ,   ，                
list_pointer Merge(list_pointer pHead1, list_pointer pHead2)
{
    if (pHead1 == NULL)
        return pHead2;
    if (pHead2 == NULL)
        return pHead1;

    list_pointer pMerge = NULL;//           
    //                
    if (pHead1->value < pHead2->value)
    {
        pMerge = pHead1;
        pMerge->link = Merge(pHead1->link, pHead2);
    }
    else
    {
        pMerge = pHead2;
        pMerge->link = Merge(pHead1, pHead2->link);//         
    }
    return pMerge;
}

3. 두 개의 링크 중 첫 번 째 공공 노드 를 찾 습 니 다.
문제 설명: 두 개의 링크 를 입력 하여 두 개의 링크 의 공공 노드 를 계산 합 니 다.
알고리즘 사상
사고 1: 만력 법, 첫 번 째 링크 를 옮 겨 다 니 며 하나의 노드 를 옮 겨 다 닐 때마다 두 번 째 링크 에서 모든 노드 를 순서대로 옮 겨 다 닌 다. 만약 에 두 번 째 링크 에 노드 와 첫 번 째 링크 의 노드 가 같다 면 공공 노드 를 찾 을 수 있다.이런 사고의 시간 복잡 도 는 O (n ^ 2) 로 효율 이 매우 낮다.사고방식 2: 먼저 공공 결점 이 있 는 두 개의 체인 테이블 의 특징 을 분석한다. 만약 에 두 개의 체인 테이블 에 공공 결점 이 존재 한다 면 두 개의 체인 테이블 에 모두 하나의 결점 이 존재 하고 그의 링크 지향 은 같다.단 방향 링크 의 모든 노드 는 하나의 방향 만 있 을 수 있 기 때문에 첫 번 째 공공 노드 부터 시작 한 후에 그들의 모든 노드 는 겹 쳐 서 더 이상 갈 라 질 수 없다.그래서 두 개의 공공 결점 이 있 고 부분 이 겹 치 는 체인 시 계 는 Y 처럼 보인다.
우선, 만약 에 두 개의 링크 에 공공 노드 가 있다 면 공공 노드 는 반드시 링크 꼬리 에 있 을 것 이 라 고 확신 할 수 있다.만약 에 두 개의 링크 의 마지막 결점 부터 비교 하면 마지막 똑 같은 결점 을 만 나 는 것 이 바로 그들의 공공 결점 이다.그러나 링크 가 마지막 노드 로 포 지 셔 닝 하려 면 처음부터 옮 겨 다 녀 야 합 니 다. 가장 먼저 옮 겨 다 니 는 노드 의 마지막 비교, 마지막 에 옮 겨 다 니 는 노드 (끝 점) 의 첫 번 째 비교 가 필요 하기 때문에 우 리 는 스 택 을 사용 할 수 있 습 니 다.먼저 두 개의 링크 를 옮 겨 다 니 며 두 개의 스 택 으로 모든 노드 를 저장 합 니 다.매번 창고 꼭대기 의 결산 점 을 비교 하여 마지막 똑 같은 결산 점 까지 비교 하 다.시간 복잡 도 O (m + m), m, n 은 각각 두 개의 링크 의 길이 이 고 공간 복잡 도 역시 O (m + n) 이다.
사고 3: 스 택 을 사용 하 는 목적 은 바로 마지막 요 소 를 찾 아서 뒤에서 옮 겨 다 니 는 것 이다.이렇게 해서 두 개의 링크 의 결산 포인트 가 일치 하지 않 을 때 끝 점 에 도착 하 는 시간 이 다르다 는 것 을 해결 했다.생각 을 바꾸다.만약 에 링크 의 길 이 를 미리 알 면 우 리 는 긴 링크 가 짧 은 링크 보다 몇 가지 요소 가 많다 는 것 을 알 수 있다. 그러면 긴 링크 가 먼저 몇 걸음 간 간 다음 에 두 개의 링크 가 동시에 뒤로 옮 겨 다 니 기 시작 하면 첫 번 째 똑 같은 노드 는 바로 공공 노드 이다.이런 사상의 시간 복잡 도 는 O (m + n) 이지 만 우 리 는 더 이상 추가 적 인 공간 보조 가 필요 하지 않다.
코드
사고 3 코드.

//      
unsigned int getLength(list_pointer p)
{
    list_pointer pNode = p;
    int length = 0;
    while (pNode)
    {
        length++;
        pNode = pNode->link;
    }
    return length;
}

//              
ListNode* FindFirstCommonNode(list_pointer pHead1, list_pointer pHead2)
{
    if (!pHead1 || !pHead2)
        return NULL;
    //         
    unsigned int nLength1 = getLength(pHead1);
    unsigned int nLength2 = getLength(pHead2);

    int nLengthDif = nLength1 - nLength2;
    list_pointer pListHeadLong = pHead1;
    list_pointer pListHeadShort = pHead2;

    if (nLength1 < nLength2)
    {
        nLengthDif = nLength2 - nLength1;
        pListHeadLong = pHead2;
        pListHeadShort = pHead1;
    }

    //      
    for (int i = 0; i < nLengthDif; i++)
    {
        pListHeadLong = pListHeadLong->link;
    }

    while (pListHeadLong && pListHeadShort
        && pListHeadLong != pListHeadShort)
    {
        pListHeadLong = pListHeadLong->link;
        pListHeadShort = pListHeadShort->link;
    }
    //         
    ListNode *theCommonNode = pListHeadLong;
    return theCommonNode;
}

총결산
이런 문제 에 부 딪 혔 을 때 일반적인 사고방식 의 해결 방법 은 우리 가 흔히 생각 할 수 있 지만 시공 효율 이 매우 낮다. 이런 효율 적 인 해결 방법 을 볼 때 나 는 정말 기묘 하고 편리 하 게 문 제 를 해결 했다 고 생각한다.우 리 는 이런 방법 에서 하나의 방향 을 배 울 수 있다. 예 를 들 어 하나의 지침 으로 해결 할 수 없 는 것 은 두 개의 지침 을 시험 해 보고 해결 해 야 할 문제 와 링크 특유 의 저장 구조의 관 계 를 정리 하 는 등 이다.이번 에는 여기까지 입 니 다. 부족 한 점 많이 가르쳐 주세요 ~