[알고리즘] 단일 체인 표 의 마지막 k 번 째 요 소 를 찾 아 라.

문제 풀이 방향:
링크 의 마지막 k 번 째 요 소 를 구하 기 위해 가장 쉽게 생각 할 수 있 는 방법 은 먼저 단일 링크 를 한 번 훑 어보 고 전체 단일 링크 의 길이 n 을 구 한 다음 에 마지막 k 번 을 양수 n - k 번 으로 바 꾸 고 이 어 한 번 훑 어보 면 결 과 를 얻 을 수 있다.그러나 이런 방법 은 체인 표를 두 번 옮 겨 다 녀 야 한다. 첫 번 째 는 단일 체인 표 의 길 이 를 구 하 는 데 사용 되 고 두 번 째 는 정수 n - k 요 소 를 찾 는 데 사용 된다. 만약 에 처음부터 끝까지 링크 의 특정한 요소 부터 k 개의 요 소 를 옮 겨 다 니 며 링크 의 끝 에 도착 하면 요 소 는 바로 찾 아야 할 마지막 k 번 째 요소 입 니 다.디자인 은 다음 과 같다. 링크 의 모든 노드 요 소 를 차례대로 테스트 하고 k 개의 요 소 를 옮 겨 다 니 며 링크 의 끝 에 도 착 했 는 지 확인 하고 마지막 k 번 째 요 소 를 찾 을 때 까지 확인한다.이 방법 은 같은 요 소 를 여러 번 반복 할 것 입 니 다. 링크 의 대부분 요 소 는 k 개의 요 소 를 옮 겨 다 녀 야 합 니 다. 만약 에 링크 의 길이 가 n 이 라면 이 알고리즘 은 시간 복잡 도 는 O (kn) 급 이 고 효율 이 너무 낮 습 니 다. 또 다른 효율 적 인 방법 이 존재 한다.찾 는 과정 에서 두 개의 지침 을 설정 하여 그 중의 한 지침 이 다른 지침 보다 k - 1 단계 먼저 이동 한 다음 에 두 지침 이 동시에 앞으로 이동 하도록 합 니 다.선 행 된 포인터 가 NULL 을 가리 킬 때 까지 순환 합 니 다. 다른 포인터 가 가리 키 는 위 치 는 찾 는 위치 입 니 다.
프로그램 은 다음 과 같 습 니 다:

public Node findElem(Node head,int k){
        if(k<1 || head == null)
        {
            return null;
        }
        Node p1 = head;
        Node p2 = head;
        for (int i = 0; i < k - 1; i++) { //  k-1 
            if(p1.next != null){
                p1 = p1.next;
            }else {
                return null;
            }

        }
        while (p1 != null) {
            p1 = p1.next;
            p2 = p2.next;
        }
        return p2;
    }

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

Java 프로그래머 면접에서의 다중 스레드 문제 요약

wait ()/notify ()/notify All () 의 모든 방법을 호출할 때, 현재 라인이 이 대상의 자물쇠를 얻지 못하면, Illegal MonitorState Exception의 이상을 던집니다. Thre...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[알고리즘] 단일 체인 표 의 마지막 k 번 째 요 소 를 찾 아 라.

좋은 웹페이지 즐겨찾기