검지 혜택: 링크 의 마지막 K 번 째 노드

4052 단어 Algorithm
검지 혜택: 링크 의 마지막 K 번 째 노드
제목 설명
링크 를 입력 하여 이 링크 의 마지막 k 번 째 노드 를 출력 합 니 다.
주의:
  • k >= 0 ;
  • k 가 링크 길이 보다 크 면 NULL 로 돌아 갑 니 다.

  • 본보기
      :  :1->2->3->4->5 ,k=2
    
      :4
    

    알고리즘 (링크 옮 겨 다 니 기) O (n)
    단일 체인 시트 는 전구 노드 로 색인 할 수 없 기 때문에 뒤로 이동 할 수 밖 에 없습니다.
  • 첫 번 째 변수 링크 는 링크 의 길이 length
  • 를 얻 을 수 있 습 니 다.
  • 마지막 k 번 째 노드, 즉 양수 length - k + 1 번 노드
  • 획득
    시공 분석
    시간 복잡 도 분석: 링크 는 두 번 반복 되 고 시간 복잡 도 는 O (n) 이다.
    C + + 코드
    /*
    struct ListNode {
    	int val;
    	struct ListNode *next;
    	ListNode(int x) :
    			val(x), next(NULL) {
    	}
    };*/
    class Solution {
    public:
        ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
            if (NULL == pListHead)
                return NULL;
            unsigned int num = 0;
            auto *node = pListHead;
            while (node)
            {
                num++;
                node = node->next;
            }
            
            node = pListHead;
            if (k > num)
                return NULL;
            
            //   num - k  
            //     node   num - k +1    
            for (int i = 0; i < num - k; i++)
            {
                node = node -> next;    
            } 
            return node;
        }
    };
    

    좋은 웹페이지 즐겨찾기