면접 에서 흔히 볼 수 있 는 링크 문제
링크 는 가장 기본 적 인 데이터 구조 로 면접 관 들 도 링크 로 면접 자의 기본 능력 을 고찰 하고 링크 와 관련 된 조작 이 상대 적 으로 간단 하 며 코드 작성 능력 도 고찰 하기에 적합 하 다.링크 의 조작 도 지침 을 떠 날 수 없고 지침 은 실 수 를 하기 쉽다.여러 가지 원인 을 종합 하면 링크 문 제 는 면접 에서 매우 중요 한 위 치 를 차지한다.본 고 는 링크 와 관련 된 면접 문 제 를 전면적으로 정리 하여 일자 리 를 찾 는 학생 들 에 게 도움 이 되 기 를 바 랍 니 다.
링크 노드 설명 은 다음 과 같 습 니 다.
struct ListNode { int m_nKey; ListNode * m_pNext;
};
제목 목록:
1. 단일 체인 테이블 의 결점 의 개 수 를 구하 십시오. 2. 단일 체인 테이블 을 반전 시 킵 니 다. 3. 단일 체인 테이블 의 마지막 K 개의 결점 찾기 (k > 0) 4. 단일 체인 테이블 의 중간 결점 찾기 5. 끝 에서 끝까지 단일 체인 테이블 인쇄 6. 이미 알 고 있 는 두 개의 단일 체인 표 pHead 1 과 pHead 2 는 각각 질서 가 있 고 이 를 하나의 체인 표 로 합 쳐 도 질서 가 있 습 니 다. 7. 하나의 단일 체인 표 에 고리 가 있 는 지 판단 합 니 다. 8. 두 개의 단일 체인 표 가 교차 하 는 지 판단 합 니 다. 9. 두 개의 단일 체인 표 가 교차 하 는 첫 번 째 노드 10. 이미 알 고 있 는 하나의 단일 체인 표 에 고리 가 존재 합 니 다.링 에 들 어 가 는 첫 번 째 노드 11. 단일 체인 헤더 포인터 pHead 와 한 노드 포인터 pToBeDeleted, O (1) 시간 복잡 도 삭제 노드 pToBeDeleted
상세 한 해답
1. 단일 체인 표 의 결산 점 의 개 수 를 구하 다.
이것 은 가장 기본 적 인 것 입 니 다. 정확 한 코드 를 신속하게 쓸 수 있 고 링크 가 비어 있 는 지 확인 할 수 있 습 니 다.시간 복잡 도 는 O (n) 이다.참조 코드 는 다음 과 같 습 니 다.
-
//
-
unsigned int GetListLength(ListNode * pHead)
-
{
-
if(pHead ==
NULL)
-
return
0;
-
-
unsigned
int nLength =
0;
-
ListNode * pCurrent = pHead;
-
while(pCurrent !=
NULL)
-
{
-
nLength++;
-
pCurrent = pCurrent->m_pNext;
-
}
-
return nLength;
-
}
2.
， ， 。 。 O（n）。 ：
-
//
-
ListNode * ReverseList(ListNode * pHead)
-
{
-
// ， ，
-
if(pHead ==
NULL || pHead->m_pNext ==
NULL)
-
return pHead;
-
-
ListNode * pReversedHead =
NULL;
// ， NULL
-
ListNode * pCurrent = pHead;
-
while(pCurrent !=
NULL)
-
{
-
ListNode * pTemp = pCurrent;
-
pCurrent = pCurrent->m_pNext;
-
pTemp->m_pNext = pReversedHead;
// ，
-
pReversedHead = pTemp;
-
}
-
return pReversedHead;
-
}
3. K （k > 0）
， ， （n-k） 。 ，k 0，k 1，k 。 O（n）。 。
， 。
， k ， k-1， ， ， k 。
：
-
// K
-
ListNode * RGetKthNode(ListNode * pHead, unsigned int k) // R
-
{
-
if(k ==
0 || pHead ==
NULL)
// k 1 ， k 0 NULL
-
return
NULL;
-
-
ListNode * pAhead = pHead;
-
ListNode * pBehind = pHead;
-
while(k >
1 && pAhead !=
NULL)
// k
-
{
-
pAhead = pAhead->m_pNext;
-
k--;
-
}
-
if(k >
1 || pAhead ==
NULL)
// k， NULL
-
return
NULL;
-
while(pAhead->m_pNext !=
NULL)
// ，
-
{
-
pBehind = pBehind->m_pNext;
-
pAhead = pAhead->m_pNext;
-
}
-
return pBehind;
// k
-
}
4.
。 ， ， ， ， ， ， ， （n/2+1） 。 ， 1 2 。 O（n）。 ：
-
// ， n(n>0)， n/2+1
-
ListNode * GetMiddleNode(ListNode * pHead)
-
{
-
if(pHead ==
NULL || pHead->m_pNext ==
NULL)
// ，
-
return pHead;
-
-
ListNode * pAhead = pHead;
-
ListNode * pBehind = pHead;
-
while(pAhead->m_pNext !=
NULL)
// ， ，
-
{
-
pAhead = pAhead->m_pNext;
-
pBehind = pBehind->m_pNext;
-
if(pAhead->m_pNext !=
NULL)
-
pAhead = pAhead->m_pNext;
-
}
-
return pBehind;
//
-
}
5.
， ， 。 ， ， ， 。 。 O（n）。 ：
：
-
// ，
-
void RPrintList(ListNode * pHead)
-
{
-
std::
stack
s;
-
ListNode * pNode = pHead;
-
while(pNode !=
NULL)
-
{
-
s.push(pNode);
-
pNode = pNode->m_pNext;
-
}
-
while(!s.empty())
-
{
-
pNode = s.top();
-
printf(
"%d\t", pNode->m_nKey);
-
s.pop();
-
}
-
}
：
-
// ，
-
void RPrintList(ListNode * pHead)
-
{
-
if(pHead ==
NULL)
-
{
-
return;
-
}
-
else
-
{
-
RPrintList(pHead->m_pNext);
-
printf(
"%d\t", pHead->m_nKey);
-
}
-
}
6. pHead1 pHead2 ，
。 ， 。 O（1） 。 O（max(len1, len2)）。 ：
-
//
-
ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
-
{
-
if(pHead1 ==
NULL)
-
return pHead2;
-
if(pHead2 ==
NULL)
-
return pHead1;
-
ListNode * pHeadMerged =
NULL;
-
if(pHead1->m_nKey < pHead2->m_nKey)
-
{
-
pHeadMerged = pHead1;
-
pHeadMerged->m_pNext =
NULL;
-
pHead1 = pHead1->m_pNext;
-
}
-
else
-
{
-
pHeadMerged = pHead2;
-
pHeadMerged->m_pNext =
NULL;
-
pHead2 = pHead2->m_pNext;
-
}
-
ListNode * pTemp = pHeadMerged;
-
while(pHead1 !=
NULL && pHead2 !=
NULL)
-
{
-
if(pHead1->m_nKey < pHead2->m_nKey)
-
{
-
pTemp->m_pNext = pHead1;
-
pHead1 = pHead1->m_pNext;
-
pTemp = pTemp->m_pNext;
-
pTemp->m_pNext =
NULL;
-
}
-
else
-
{
-
pTemp->m_pNext = pHead2;
-
pHead2 = pHead2->m_pNext;
-
pTemp = pTemp->m_pNext;
-
pTemp->m_pNext =
NULL;
-
}
-
}
-
if(pHead1 !=
NULL)
-
pTemp->m_pNext = pHead1;
-
else
if(pHead2 !=
NULL)
-
pTemp->m_pNext = pHead2;
-
return pHeadMerged;
-
}
：
-
ListNode * MergeSortedList(ListNode * pHead1, ListNode * pHead2)
-
{
-
if(pHead1 ==
NULL)
-
return pHead2;
-
if(pHead2 ==
NULL)
-
return pHead1;
-
ListNode * pHeadMerged =
NULL;
-
if(pHead1->m_nKey < pHead2->m_nKey)
-
{
-
pHeadMerged = pHead1;
-
pHeadMerged->m_pNext = MergeSortedList(pHead1->m_pNext, pHead2);
-
}
-
else
-
{
-
pHeadMerged = pHead2;
-
pHeadMerged->m_pNext = MergeSortedList(pHead1, pHead2->m_pNext);
-
}
-
return pHeadMerged;
-
}
7.
。 ， ， 。 ， ， ， ， ， 。 O（n）。 ：
-
bool HasCircle(ListNode * pHead)
-
{
-
ListNode * pFast = pHead;
//
-
ListNode * pSlow = pHead;
//
-
while(pFast !=
NULL && pFast->m_pNext !=
NULL)
-
{
-
pFast = pFast->m_pNext->m_pNext;
-
pSlow = pSlow->m_pNext;
-
if(pSlow == pFast)
// ，
-
return
true;
-
}
-
return
false;
-
}
8.
， 。 ， ， 。 ， ， ， ， ， ， 。 O(len1+len2)， ， O(1)。 ：
-
bool IsIntersected(ListNode * pHead1, ListNode * pHead2)
-
{
-
if(pHead1 ==
NULL || pHead2 ==
NULL)
-
return
false;
-
-
ListNode * pTail1 = pHead1;
-
while(pTail1->m_pNext !=
NULL)
-
pTail1 = pTail1->m_pNext;
-
-
ListNode * pTail2 = pHead2;
-
while(pTail2->m_pNext !=
NULL)
-
pTail2 = pTail2->m_pNext;
-
return pTail1 == pTail2;
-
}
9.
， len1， 。
， len2， ， ， ， 。
， len1 len2， len1-len2 ， ， ， 。
，O(len1+len2)。 ：
-
ListNode* GetFirstCommonNode(ListNode * pHead1, ListNode * pHead2)
-
{
-
if(pHead1 ==
NULL || pHead2 ==
NULL)
-
return
NULL;
-
-
int len1 =
1;
-
ListNode * pTail1 = pHead1;
-
while(pTail1->m_pNext !=
NULL)
-
{
-
pTail1 = pTail1->m_pNext;
-
len1++;
-
}
-
-
int len2 =
1;
-
ListNode * pTail2 = pHead2;
-
while(pTail2->m_pNext !=
NULL)
-
{
-
pTail2 = pTail2->m_pNext;
-
len2++;
-
}
-
-
if(pTail1 != pTail2)
// NULL
-
return
NULL;
-
-
ListNode * pNode1 = pHead1;
-
ListNode * pNode2 = pHead2;
-
// ，
-
if(len1 > len2)
-
{
-
int k = len1 - len2;
-
while(k--)
-
pNode1 = pNode1->m_pNext;
-
}
-
else
-
{
-
int k = len2 - len1;
-
while(k--)
-
pNode2 = pNode2->m_pNext;
-
}
-
while(pNode1 != pNode2)
-
{
-
pNode1 = pNode1->m_pNext;
-
pNode2 = pNode2->m_pNext;
-
}
-
return pNode1;
-
}
10. ，
， 。 （ ）， ， 。 ：
-
ListNode* GetFirstNodeInCircle(ListNode * pHead)
-
{
-
if(pHead ==
NULL || pHead->m_pNext ==
NULL)
-
return
NULL;
-
-
ListNode * pFast = pHead;
-
ListNode * pSlow = pHead;
-
while(pFast !=
NULL && pFast->m_pNext !=
NULL)
-
{
-
pSlow = pSlow->m_pNext;
-
pFast = pFast->m_pNext->m_pNext;
-
if(pSlow == pFast)
-
break;
-
}
-
if(pFast ==
NULL || pFast->m_pNext ==
NULL)
-
return
NULL;
-
-
// ，
-
ListNode * pAssumedTail = pSlow;
-
ListNode * pHead1 = pHead;
-
ListNode * pHead2 = pAssumedTail->m_pNext;
-
-
ListNode * pNode1, * pNode2;
-
int len1 =
1;
-
ListNode * pNode1 = pHead1;
-
while(pNode1 != pAssumedTail)
-
{
-
pNode1 = pNode1->m_pNext;
-
len1++;
-
}
-
-
int len2 =
1;
-
ListNode * pNode2 = pHead2;
-
while(pNode2 != pAssumedTail)
-
{
-
pNode2 = pNode2->m_pNext;
-
len2++;
-
}
-
-
pNode1 = pHead1;
-
pNode2 = pHead2;
-
// ，
-
if(len1 > len2)
-
{
-
int k = len1 - len2;
-
while(k--)
-
pNode1 = pNode1->m_pNext;
-
}
-
else
-
{
-
int k = len2 - len1;
-
while(k--)
-
pNode2 = pNode2->m_pNext;
-
}
-
while(pNode1 != pNode2)
-
{
-
pNode1 = pNode1->m_pNext;
-
pNode2 = pNode2->m_pNext;
-
}
-
return pNode1;
-
}
11. pHead pToBeDeleted，O(1) pToBeDeleted
， ， ， O(n)。 ， ， ， 。 ， ， ， O(1)。 ：
-
void Delete(ListNode * pHead, ListNode * pToBeDeleted)
-
{
-
if(pToBeDeleted ==
NULL)
-
return;
-
if(pToBeDeleted->m_pNext !=
NULL)
-
{
-
pToBeDeleted->m_nKey = pToBeDeleted->m_pNext->m_nKey;
// ，
-
ListNode * temp = pToBeDeleted->m_pNext;
-
pToBeDeleted->m_pNext = pToBeDeleted->m_pNext->m_pNext;
-
delete temp;
-
}
-
else
//
-
{
-
if(pHead == pToBeDeleted)
//
-
{
-
pHead =
NULL;
-
delete pToBeDeleted;
-
}
-
else
-
{
-
ListNode * pNode = pHead;
-
while(pNode->m_pNext != pToBeDeleted)
//
-
pNode = pNode->m_pNext;
-
pNode->m_pNext =
NULL;
-
delete pToBeDeleted;
-
}
-
}
-
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 단일 체인 테이블의 순환과 귀속 실현을 반전시키다텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
