leetcode 링크 관련 문제 풀이 방법

예전 에 leetcode 를 닦 았 는데 많은 링크 의 제목 이 느 리 고 힘 들 었 습 니 다. 결국 링크 라 는 데이터 구조 에 대해 불 신 감 을 느 꼈 습 니 다. 한 노드 를 지나 갈 때마다 돌아 갈 방법 이 없 었 기 때 문 입 니 다. 평소에 배열 에 익숙 했 기 때문에 이런 변화 에 적응 하지 못 했 습 니 다.
여기 서 제 가 문 제 를 푸 는 과정 에서 링크 와 관련 된 문 제 를 해결 하 는 데 사용 하 는 기술 과 링크 를 어떻게 잘 사용 하 는 지 말씀 드 리 겠 습 니 다.
1. Dummy Head
leetcode 에서 들 어 오 는 head 는 데이터 가 있 습 니 다. 이것 은 노드 가 head 를 가리 키 지 않 기 때문에 head 에 대한 수정 이 가끔 번 거 로 울 수 있 습 니 다. 따라서 가상 노드 가 head 를 가리 키 고 나중에 head 로 돌아 가 야 할 때 바로 돌아 갈 수 있 습 니 다. Dummy Head - > next.

ListNode* dummyhead = &ListNode(-1);

이 기 교 는 아마 가장 자주 사용 하 는 것 일 것 이다.
2. 체인 끊 기
이 조작 은 함수 cut (l, n) 을 통 해 이 루어 집 니 다. 그 역할 은 링크 l 을 앞의 n 개 노드 를 자 르 고 후반 부분의 체인 헤더 로 돌아 가 는 것 입 니 다.

//    head  n      ，           
ListNode* cut(ListNode* head, int n) {
	ListNode *p = head;
	while (p != NULL && --n)
		p = p->next;
	if (p == NULL)
		return NULL;
	ListNode *q = p->next;
	p->next = NULL;
	return q;
}

이 조작 은 매우 중요 하 다. 왜냐하면 실제 적 으로 문제 가 우리 에 게 체인 헤드 를 주 고 우리 에 게 이 체인 시트 에 대해 어떤 조작 을 해 야 하 는 지 알려 줄 때 우 리 는 헤드 의 앞 에 무엇이 있 는 지 모 르 고 알 방법 도 없다. 왜냐하면 주 는 체인 시트 는 단 방향 이기 때문이다.
한편, 이 체인 작업 은 문제 의 규 모 를 줄 일 수 있다. 체인 의 길이 가 n 이 라 고 가정 하면 체인 을 끊 은 후에 얻 은 체인 의 길 이 는 m 이 고 원래 의 문제 규모 에 비해 많이 줄 어 들 었 다. 이것 은 많은 문제 들 이 분 치 법 으로 할 수 있다 는 것 을 의미한다.
문제 의 규모 가 어느 정도 줄 어 들 면 바로 해결 할 수 있다. 우 리 는 모든 해결 한 하위 문 제 를 합병 함으로써 원래 의 문 제 를 해결 할 수 있다.
합병
전에 말 했 듯 이 분 치 법 을 사용 하 는데 그 중에서 관건 적 인 단 계 는 모든 하위 문 제 를 합병 하 는 것 이다.일반 링크 의 합병 방법 은 앞 뒤 가 서로 연결 되 는 것 이다. 이것 은 할 말 이 없다. 여기 서 질서 있 는 링크 의 합병 을 말한다.

//                   
ListNode* merge(ListNode* list1, ListNode* list2) {
	ListNode dummyHead(-1);
	ListNode *p = &dummyHead;
	
	while (list1 != NULL && list2 != NULL) {
		if (list1->val > list2->val) {
			p->next = list2;
			list2 = list2->next;
			p = p->next;
		}
		else {
			p->next = list1;
			list1 = list1->next;
			p = p->next;
		}
	}
	if (list1)
		p->next = list1;
	if (list2)
		p->next = list2;
	return dummyHead.next;
}

4. 빠 르 고 느 린 지침
무엇이 빠 르 고 느 린 지침 입 니까?
두 개의 지침 을 정의 하 는 것 이다. 한 지침 (느 린 지침) 의 이동 속 도 는 v 이 고 다른 지침 (빠 른 지침) 속 도 는 2v 이다. 그러면 같은 시간 을 거 쳐 빠 른 지침 이 걸 어 가 는 거 리 는 느 린 지침 의 2 배 이다.
C + + 코드:

        ListNode *fast = head, *slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }