링크 지식 포인트 정리 (2) 더 블 링크, 순환 링크 의 정리 와 일부 LeetCode 의 링크 제목 추천

다음 링크 지식 정리 (1) 이번 에는 싱글 링크 의 확장 인 더 블 링크, 순환 링크, 그리고 제 가 개인 적 으로 비교적 좋다 고 생각 하 는 링크 연습 문제 인 LeetCode 를 추천 합 니 다.
 
더 블 링크 의 간단 한 요약
더 블 링크 는 바로 노드 의 정의 에 prev 포인터 가 위의 노드 를 가리 키 는 것 이다. 앞장 서 는 노드 의 더 블 링크 에 있어 머리 노드 의 prev 지침 은 NULL 을 가리 키 는 것 이다.여 기 는 더 이상 각종 실현 을 일일이 열거 하지 않 는 다.
특히 더 블 링크 에 있어 함수 링크 (Node * l, Node * r) 를 정의 할 수 있 습 니 다. 기능 은 노드 l 과 노드 r 를 연결 하고 코드 실현 입 니 다.

inline void link(Node *l, Node *r)
{
	if (l)
		l->next = r;
	if (r)
		r->prev = l;
}

만약 우리 에 게 이런 링크 가 있다 면  a - > b - > c, 나 는 b 의 위치 (즉 a 의 뒤에) 에 요소 new Node 를 삽입 하려 고 한다. 만약 우리 가 link 함 수 를 사용한다 면, 우 리 는 매우 간결 하 게 두 번 의 link 함 수 를 호출 해 야 한다.

link(newNode,a->next);//      b
link(a,newNode);//  a    

위의 두 줄 코드 에 대해 a 가 끝 점 이 라면 링크 도 틀 리 지 않 습 니 다. 링크 의 실현 에서 l 과 r 에 대해 빈 논리 가 있 기 때문에 l 과 r 가 NULL 이 든 아니 든 틀 리 지 않 습 니 다.링크 함수 분리 논 리 를 사용 하면 코드 의 논 리 를 더욱 명확 하 게 할 수 있 습 니 다. 특히 뒤에 순환 더 블 링크 를 쓸 때 논리 적 으로 링크 함수 만 호출 하면 복잡 한 연결 작업 을 완성 할 수 있 습 니 다.
 
순환 링크 의 간단 한 요약
순환 링크 는 바로 꼬리 노드 가 NULL 을 가리 키 지 않 고 머리 노드 를 가리 키 는 링크 이다. 순환 링크 는 '순환' 개념 을 가 진 문 제 를 해결 하 는 데 사용 할 수 있다. 예 를 들 어 조세 프 문제 등 이다.순환 체인 테이블 의 각종 조작의 실현 과 단일 체인 테이블 의 실현 차 이 는 많 지 않다. 다만 주의해 야 할 것 은 선두 노드 의 순환 체인 테이블 은 옮 겨 다 닐 때 첫 번 째 데이터 노드 부터 시작 해 야 한다. 바늘 로 한 바퀴 훑 은 후에 머리 노드 를 가리 키 는 것 을 중지 조건 으로 하고 순환 체인 테이블 의 옮 겨 다 니 는 것 을 예 로 들 면 현대 코드 는 다음 과 같다.

void print(Node* header)
    {
        Node *cur = header->next;//            
        while (cur != header)//cur    header   
        {
            cout << cur->data << " ";
            cur = cur->next;
        }
        cout << endl;
    }

순환 더 블 링크 는 간단 한 단일 링크 에 비해 O (1) 의 시간 복잡 도 로 특정한 노드 의 앞 노드 (prev 포인터 이용) 를 얻 을 수 있 고 간단 한 단일 링크 는 O (n) 의 시간 복잡 도 (처음부터 다시 한 번 얻 을 수 있다) 가 필요 하 다. 이 를 제외 하고 링크 에서 특정한 위치 에 있 는 노드 를 찾 으 려 면순환 더 블 링크 는 색인 이 양 끝 에서 멀리 떨 어 진 곳 에 따라 처음부터 끝까지 옮 겨 다 니 거나 꼬리 에서 머리 로 옮 겨 다 니 는 것 을 선택 할 수 있 습 니 다. 그러면 실제 요 소 를 찾 는 시간 복잡 도 는 O (n / 2) 가 됩 니 다. 단일 링크 보다 처음부터 옮 겨 다 니 는 것 이 좋 지만 결국은 O (n) 입 니 다.실제 개발 에서 체인 시 계 를 사용 하려 면 보통 간단 한 단일 체인 시 계 를 대체 하여 효율 을 높 인 다.
 
 LeetCode 링크 관련 제목 추천
제 가 추천 하 는 문 제 는 모두 중국어 LeetCode 사이트 의 문제 입 니 다. 사이트 주소: 힘 의 단추 이 고 추천 하 는 것 은 모두 난이도 가 간단 합 니 다. - 중간 정도 의 연습 문제 입 니 다. 제 가 추천 하 는 것 은 모두 일정한 사 고 량 과 일정한 인 코딩 능력 이 있어 야 해결 할 수 있 는 문제 라 고 생각 할 수 있 습 니 다. 하지만 어렵 지 않 고 초보 자 도 할 수 있 습 니 다.저 는 개인 적 으로 이런 문 제 는 효율 적 이 고 간결 한 코드 로 문 제 를 해결 하 는 방법 을 배 워 야 한다 고 생각 합 니 다. 즉, 인 코딩 능력 에 약간 편중 되 는 문제 입 니 다. 체인 표 지식 점 에 중심 을 두 는 문제 이기 때 문 입 니 다.
 
2. 두 수 를 더 하 다
이 문 제 는 덧셈 계산 을 모 의 한 문제 로 문제 가 준 링크 순 서 를 자세히 읽 고 먼저 자신의 코드 로 실현 한 다음 에 코드 를 가장 간결 한 형식 으로 쓰 는 방법 을 연습 하 는 데 중심 을 둔다.
 
147. 링크 삽입 정렬
링크 삽입 정렬 문제.
 
237. 링크 의 노드 삭제
간단 한 문 제 는 커 브 를 돌려 야 정세 사 고 를 버 려 야 해결 방법 을 생각 할 수 있다.
 
141. 링 링크
링크 에 고리 가 있 는 지 없 는 지 판단 하 는 템 플 릿 문 제 는 비교적 전형 적 이다.
 
21. 두 개의 질서 있 는 링크 를 합 친다.
링크 의 2 번 병합 은 비교적 간단 하 므 로 일정한 인 코딩 능력 이 필요 하 다.
 
206. 반전 링크
반전 링크 의 템 플 릿 문 제 는 문제 자체 가 간단 하 므 로 재 귀적 으로 해결 하 는 것 을 추천 합 니 다.
 
24. 두 개의 교환 링크 의 노드
중간 문제, 일정한 인 코딩 능력 이 필요 합 니 다.
 
876. 링크 의 중간 노드
면접 에서 흔히 볼 수 있 는 문제, 빠 르 고 느 린 지침 의 전형 적 인 문제.
 
이상 의 문 제 는 제 가 비교적 전형 적 이 고 어렵 지 않 은 문 제 를 풀 었 기 때문에 초보 자 들 이 연습 하기에 적합 합 니 다. 만약 에 문 제 를 계속 풀 려 면 LeetCode 에 올 라 문 제 를 풀 고 문 제 를 많이 풀 어야 자신의 능력 을 빨리 향상 시 킬 수 있 습 니 다.