면접 에서 흔히 볼 수 있 는 링크 문제 집합
6768 단어 데이터 구조 와 알고리즘
typedef struct ListNode
{
int data;
ListNode* next;
}ListNode;
1. 단일 체인 표 의 노드 의 개 수 를 계산한다.
int GetListLength(ListNode* pHead)
{
if(NULL==pHead)
{
return 0;
}
unsigned int nLength=0;
ListNode* p=pHead;
while(p)
{
++nLength;
p=p->next;
}
return nLength;
}2. 싱글 체인 시트 의 반전
하나의 노드 나 링크 만 비어 있 는 상황 을 판단 하고 인접 한 노드 의 next 지침 을 순환 적 으로 옮 겨 다 니 며 교환 하면 됩 니 다. 시간 복잡 도 는 O (n) 입 니 다.
ListNode* ListReverse(ListNode* pHead)
{
if(NULL==pHead||NULL==pHead->next)
{
return pHead;
}
ListNode* p=pHead;
ListNode* q=p->next;
ListNode* r;
while(q)
{
r=p->next;
q->next=p;
p=q;
q=r;
}
pHead->next=NULL;
pHead=p;
return pHead;
}
3. 단일 체인 테이블 의 마지막 k 번 째 노드 찾기
이 문 제 는 먼저 링크 를 옮 겨 다 니 며 링크 의 길이 n 을 계산 한 다음 에 n - k 의 결점 을 찾 을 수 있 습 니 다.
우 리 는 또 거꾸로 생각 할 수 있다. 두 개의 지침, p, q 를 통 해.p 와 q 는 동시에 머리 결점 을 가리 키 고 p 지침 은 먼저 k 보 를 간 다음 에 p 와 q 가 함께 간다. 이렇게 p 는 n - k 보 를 걸 어서 링크 의 끝 에 도착 하고 q 는 n - k 의 결점, 즉 마지막 k 의 결점, 시간 복잡 도 는 O (n) 보다 작다. 주의: 임계 상황 의 판단.
ListNode* GetRkNode(ListNode* pHead,unsigned int k)
{
if(k==0||NULL==pHead)
{
return NULL;
}
ListNode* p=pHead;
ListNode* q=pHead;
unsigned int i;
while (q)
{
++i;
if(i==k)
{
break;
}
q=q->next;
}
if(inext;
q=q->next;
}
return p;
}
4. 단일 체인 테이블 의 중간 지점 찾기
이 문 제 는 두 개의 지침 을 사용 하 는 방식 이다. 첫 번 째 지침 은 매번 2 보 를 걷 고 두 번 째 지침 은 매번 1 보 를 걷는다. 첫 번 째 지침 이 링크 의 끝 에 도착 하면 두 번 째 지침 은 중간 노드 에 딱 도착한다.
ListNode* GetMidNode(ListNode* pHead)
{
if(NULL==pHead||NULL==pHead->next)
{
return pHead;
}
ListNode* p=pHead;
ListNode* q=pHead;
while (p)
{
p=p->next->next;
q=q->next;
}
return q;
}5. 끝 에서 끝까지 단일 체인 시트 인쇄
끝 에서 앞으로 단일 체인 표를 인쇄 하면 우 리 는 스 택 의 특성 을 빠르게 생각 할 수 있 습 니 다. 먼저 스 택 에 들 어가 서 마지막 으로 꺼 내 서 인쇄 할 수 있 습 니 다.
void RPrintfNode(ListNode* pHead)
{
if(NULL==pHead)
{
return;
}
std::stack stackNode;
while (pHead)
{
stackNode.push(pHead->data);
pHead=pHead->next;
}
while(!stackNode.empty())
{
int data=stackNode.top();
printf("%d",data);
stackNode.pop();
}
}
6. 이미 알 고 있 는 두 개의 단일 체인 표 는 어 릴 때 부터 큰 순서 로 그들 을 합병 한 후에 도 질서 가 있다 (체인 표 의 병합 정렬).
먼저 임계 조건 의 판단 에 주의해 야 한다. 하나의 링크 가 끝 에 도착 할 때 까지 비교 링크 를 옮 겨 다 니 고 남 은 빈 노드 를 새로운 링크 꼬리 에 추가 하면 된다. 원시 적 인 공간 을 이용 해 야 한다.
ListNode* MergeList(ListNode* pHead1,ListNode* pHead2)
{
if(NULL==pHead1)
{
return pHead2;
}
if(NULL==pHead2)
{
return pHead1;
}
if(NULL==pHead1&&NULL==pHead2)
{
return NULL;
}
ListNode* p=pHead1;
ListNode* q=pHead2;
ListNode* pNewNode=NULL;
ListNode* pHead;
while(p!=NULL&&q!=NULL)
{
if(p->data>q->data)
{
if(pNewNode==NULL)
{
pNewNode=q;
pHead=q;
q=q->next;
}
else
{
pNewNode->next=q;
pNewNode=q;
q=q->next;
}
}
else
{
if(pNewNode==NULL)
{
pNewNode=p;
pHead=p;
p=p->next;
}
else
{
pNewNode->next=p;
pNewNode=p;
p=p->next;
}
}
}
if(p!=NULL)
{
pNewNode->next=p;
}
if(q!=NULL)
{
pNewNode->next=q;
}
return pHead;
}7. 하나의 링크 에 고리 가 있 는 지 판단 합 니 다.
만약 에 링크 에 고리 가 존재 한다 면 두 개의 지침 을 사용 하여 첫 번 째 로 1 번 을 걸 을 수 있 고 두 번 째 는 2 걸음 을 걸 을 수 있 으 며 두 개의 지침 이 만나면 고리 가 존재 할 것 이다.
bool IsExitLoop(ListNode* pHead)
{
if(NULL==pHead)
{
return false;
}
ListNode* p=pHead;
ListNode* q=pHead;
while(p!=NULL&&q->next!=NULL)
{
p=p->next;
q=q->next->next;
if(p==q)
{
return true;
}
}
return false;
}8. 두 개의 단일 체인 표 가 교차 하 는 지 판단 한다.
주의: 만약 에 두 개의 링크 가 교차 하면 두 개의 링크 의 꼬리 노드 가 똑 같 을 것 이 므 로 두 개의 링크 의 꼬리 노드 가 똑 같은 지 판단 하면 됩 니 다.
bool IsIntersect(ListNode* pHead1,ListNode* pHead2)
{
if(NULL==pHead1||NULL==pHead2)
{
return false;
}
while (pHead1->next!=NULL)
{
pHead1=pHead1->next;
}
while(pHead2->next!=NULL)
{
pHead2=pHead2->next;
}
if(pHead1==pHead2)
{
return true;
}
return false;
}9. 단일 체인 표 가 교차 하 는 첫 번 째 교점 을 구한다.
단일 체인 표 가 교차 하 는 교점 을 구 합 니 다. 우 리 는 주로 두 개의 체인 표 의 길 이 를 모 릅 니 다. 체인 표 1 의 길 이 는 length 1 이 고 체인 표 2 의 길 이 는 length 2 라 고 가정 합 니 다. 만약 에 length 1 > length 2 라면 체인 표 1 을 먼저 length 1 - length 2 단계 로 가게 하고 체인 표 2 를 처음부터 함께 걷 게 하면 그들 이 같 으 면 만 나 는 노드 입 니 다.
ListNode* GetFirstIntersect(ListNode* pHead1,ListNode* pHead2)
{
if(pHead1==NULL||pHead2==NULL)
{
return NULL;
}
unsigned int length1=0,length2=0;
ListNode* p=pHead1;
ListNode* q=pHead2;
while(p->next!=NULL)
{
p=p->next;
++length1;
}
while(q->next!=NULL)
{
q=q->next;
++length2;
}
if(p!=q)
{
return NULL;
}
p=pHead1;
q=pHead2;
if(length1>length2)
{
p=pHead1;
unsigned int k=length1-length2;
while(k)
{
p=p->next;
k--;
}
}
else
{
q=pHead2;
unsigned int k=length2-length1;
while(k)
{
q=q->next;
k--;
}
}
while(p==q)
{
p=p->next;
q=q->next;
return p;
}
return NULL;
}10. 이미 알 고 있 는 단일 체인 표 에 링 이 존재 하 므 로 링 의 첫 번 째 노드 에 들 어가 야 합 니 다.
단일 체인 테이블 에 존재 하 는 고 리 는 위 에서 소개 한 방법 을 통 해 판단 할 수 있 습 니 다. 두 개의 바늘, 하나의 느 린 바늘 p, 하나의 빠 른 바늘 q, p 는 매번 한 걸음 씩 걷 고 q 는 매번 두 걸음 씩 걷 습 니 다. p 와 q 가 만 났 을 때 체인 테이블 에 고리 가 존재 한 다 는 것 을 설명 합 니 다.
만 나 는 노드 pNode 를 기록 한 다음 에 체인 헤드 포인터 와 pNode 에서 한 걸음 씩 걸 을 때마다 두 포인터 가 만 날 때 바로 링 의 입구 점 입 니 다.
4. 567913. 10 번 문제 의 증명 은 다음 과 같다.
pfast 가 pslow 와 만 났 을 때 pslow 는 링크 를 다 훑 어보 지 않 았 을 것 입 니 다. pfast 는 링 안에서 n 링 (1 < = n) 을 순환 하 였 습 니 다.pslow 가 s 보 를 걸 었 다 고 가정 하면 pfast 는 2s 보 (pfast 보 수 는 s 와 링 에 많이 돌아 가 는 n 권) 를 걸 었 고 링 의 길 이 를 r 로 설정 하면:
2s = s + nr s = nr 는 전체 링크 길이 L 을 설정 하고 입구 고리 와 만 남 점 거 리 는 x 이 며 출발점 에서 링 입구 점 까지 의 거 리 는 a 이다.
a + x = nr 는 a + x = (n – 1) r + r = (n - 1) r + L - a = (n - 1) r + (L – a – x)
(L – a – x) 는 만 남 점 에서 링 입구 점 까지 의 거 리 를 알 수 있 습 니 다. 이 를 통 해 알 수 있 듯 이 링크 헤드 에서 링 입구 점 까지 는 (n - 1) 순환 내부 고리 + 만 남 점 에서 링 입구 점 까지 입 니 다. 그래서 우 리 는 체인 헤드, 만 남 점 에서 각각 지침 을 설정 하고 한 걸음 씩 걸 을 때마다 두 개의 지침 이 반드시 만 나 고 만 남 의 첫 번 째 점 은 링 입구 점 입 니 다.
요약: 링크 는 면접 에서 자주 등장 하 는 면접 문제 로 기초 지식의 육성 을 중시 하고 흔히 볼 수 있 는 문 제 를 잘 알 면 능숙 해 질 것 이다.시간 관계 로 인해 상기 코드 는 테스트 사례 를 하지 않 았 습 니 다. 만약 에 오류 가 있 으 면 독자 의 지적 을 바 랍 니 다. 그리고 많이 포함 되 어 있 습 니 다.
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[JAVA] 배열 회전 출력요소 가 출력 을 시작 하 는 위치 에 주의 하 십시오. 모두 몇 라운드 의 수출 이 있 습 니까? n/2 + 1 매 라 운 드 는 상, 우, 하, 좌 로 나 뉜 다. 각 방향의 시작 위치 와 좌표 의 관 계 를 구...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
