검 지 offer JZ 14: 체인 테이블 의 마지막 k 번 째 결점

2960 단어 검지 제공
검 지 offer JZ 14: 체인 테이블 의 마지막 k 번 째 결점
문제.
링크 를 입력 하여 이 링크 의 마지막 k 번 째 노드 를 출력 합 니 다.
사고의 방향
우선, 문 제 를 보 는 첫 번 째 반응 은 링크 의 모든 노드 를 순서대로 목록 에 출력 한 다음 에 목록 의 마지막 k 항 을 출력 하면 되 지만 0 (N) 의 공간 을 소모 해 야 한 다 는 것 이다.
여기 서 매우 교묘 한 더 블 포인터 알고리즘 을 사용 합 니 다. 마지막 k 항 을 출력 하려 면 하나의 포인터 가 k - 1 항 을 먼저 달리 게 하고 두 개의 포인터 가 동시에 뒤로 이동 하 게 해 야 합 니 다. 첫 번 째 포인터 가 팀 의 끝 에 도 착 했 을 때 두 번 째 포인터 가 가리 키 는 것 은 바로 마지막 k 항 입 니 다.
k > n 등 특수 상황 에 대한 토론 에 주의 하 세 요.
코드 및 해석
class Solution:
    def FindKthToTail(self, head, k):
        # write code here
        if head == None:
            return None
        if k <= 0:
            return None
        p1, p2 = head, head
        i = 1
        while i < k:
            i += 1
            if p1.next:
                p1 = p1.next
            else:
                return None
        while p1.next:
            p1 = p1.next
            p2 = p2.next
        return p2

좋은 웹페이지 즐겨찾기