규방 의 외 사슬 표 와 사랑 을 기다리다.

제목 출처, 대기 규방 중, 오리지널 @ 진리 인, 위 챗 공식 계 정 '대기 규방 중' 에 계속 관심 가 져 주시 기 바 랍 니 다.
원제: 두 개의 단일 체인 시트 (singly linked list), 각 노드 에 0 - 9 의 숫자 를 입력 하면 두 개의 대수 에 해당 합 니 다.그리고 이 두 수의 합 (새 list) 을 되 돌려 줍 니 다.이 두 입력 의 list 길 이 는 같다.요 구 는: 귀속 할 필요 가 없다.요구 알고리즘 은 가장 좋 은 상황 에서 두 개의 list 를 한 번 만 옮 겨 다 니 고 최 악의 경우 두 번 만 옮 겨 다 니 도록 합 니 다.
분석: 만약 에 링크 가 나타 내 는 수량 이 낮은 것 에서 높 은 위치 로 표시 된다 면 매우 간단 하 다.높 은 곳 에서 낮은 곳 까지 라면 문제 가 복잡 하고, 진 위 는 모든 악의 근원 이다.
두 개의 단일 체인 표 는 각 노드 에 0 - 9 의 숫자 를 저장 하면 하나의 단일 체인 표 는 하나의 큰 수 를 나타 낸다.높 은 위치 에서 낮은 위치 로 저장 하 는 것, 즉 표 두 가 대응 하 는 것 은 이 대수 의 가장 높 은 위치 이다.두 개의 링크 의 길이 가 같 습 니 다. 우 리 는 새로운 단일 링크 를 되 돌려 야 합 니 다. 이 두 개의 입력 링크 가 대표 하 는 수의 합 입 니 다.우 리 는 재 귀 를 사용 할 수 없고 추가 저장 공간 을 사용 할 수 없다. 즉, 공간 복잡 도 는 O (1) 이다.링크 를 한 번 만 옮 겨 다 니 며 출력 링크 도 단일 링크 입 니 다.두 개의 입력 링크 를 한 번 만 옮 겨 다 닐 수 있 으 니 높 은 자리 에서 시작 합 시다.이런 제한 조건 하에 서 이것 이 유일한 길이 다.그래서?진 위 는 어떻게 정 합 니까?먼저 높 은 자 리 를 올 리 고 낮은 자 리 를 더 하면 낮은 위치 에서 발생 하 는 진 위 는 어떻게 높 은 위치 로 올 립 니까?우리 앞 방향 지침 없어.앞 방향 지침 이 없 는 이상 우 리 는 임시 지침 으로 높 은 위 치 를 가리 키 게 하고 낮은 위치 에 진 위 를 더 할 때 우 리 는 높 은 위 치 를 조작 할 수 있다.그림 을 보 여 주세요.

    1： 1 2 3     2： 1 2 8     ：  2 4     ： p q 

출력 링크 의 현재 노드 를 가리 키 는 포인터 q 가 3 + 8 = 11 을 발견 하면 진 위 를 만 들 고 높 은 비트 를 가리 키 는 p 는 노드 값 을 1 로 추가 합 니 다.주의 하 세 요. 0 - 9 의 수 를 더 하면 들 어가 지 않 거나 1 로 들 어가 거나 두 가지 상황 만 있 습 니 다.따라서 우 리 는 진위 가 다른 수 라 는 점 을 고려 하지 않 아 도 된다 는 점 이 중요 하 다. 나중에 볼 수 있 을 것 이다.이렇게 하면 돼 요?물론 아니 야, 만약 네가 연속 진 위 를 만난다 면 어떻게 깨 뜨 릴 거 야?아래 의 상황 을 보십시오.

    1： 1 2 3 4 5     2： 1 7 6 5 9

분명 한 것 은 높 은 위 치 를 가리 키 는 지침 p 는 항상 현재 결점 을 가리 키 는 지침 q 를 따라 가 서 는 안 된다. 그러면 연속 적 인 진 위 를 만 났 을 때 p 보다 높 은 위치 도 바 뀌 어야 한다.p 가 q 를 바짝 따라 갈 수 없 는 이상, 우 리 는 그것들 을 바짝 붙 이지 못 하 게 하고, 그것들 에 게 약간의 거 리 를 만들어 준다.어떤 상황 에서 연속 진 위 를 할 수 있 는 지 생각해 보 세 요.9! 응, 9 를 만 났 을 때.그것 은 어느 분 까지 연속 으로 들 어 가 려 고 합 니까?9 가 아 닌 그 분.따라서 포인터 p 는 9 가 아 닌 사람 에 게 머 물 러 그림 을 봐 야 한다.

    1： 1 2 3 4 5     2： 1 7 6 5 9     ： 2 9 9 9     ：  p       q 

이번 에는 q 가 진 위 를 해 야 한 다 는 것 을 발 견 했 을 때 p 가 가리 키 는 결점 에 1 을 더 한 다음 에 p, q 간 의 결점 을 모두 0 으로 놓 으 면 된다.왜 모두 0 을 두 었 을 까? 왜냐하면 진 위 는 1, 9 + 1 = 10 일 수 있 기 때문에 이 자리 에 남 은 것 은 당연히 0 이기 때문이다.분석 이 끝나 면 이런 방법 은 언제든지 링크 를 한 번 만 옮 겨 다 니 며 입력 해 야 한다. 공간 복잡 도 O (1).구체 적 인 코드 는 다음 과 같다.

#include<iostream>
#include<memory.h>
using namespace std;

struct Node
{
	int val;
	struct Node* next;
	Node(int x):val(x),next(NULL){}
};

Node* AddLinkList(Node* head1,Node* head2)
{
	if(head1 == NULL)return head2;
	if(head2 == NULL)return head1;
	Node* head = new Node(head1->val+head2->val);//    
	Node* p1 = head1->next,*p2 = head2->next,*p,*q = head,*pre=head;//q          
	while(p1 && p2)
	{
		int sum = p1->val+p2->val;
		p = new Node(sum % 10);
		pre->next = p;
		pre = p;
		if(sum > 9)
		{
			q->val += 1;
			for(q=q->next;q!=p;q=q->next)q->val = 0;//p   1，   9  0
		}
		else if(sum < 9)q = p;//            p
		p1 = p1->next;
		p2 = p2->next;
	}
	if(head->val > 9)
	{
		p = new Node(1);
		p->next = head;
		head->val -= 10;
		head = p;
	}
	return head;
}

Node* MakeLinkedList(int* data,int n)
{
	if(data == NULL || n<=0)return NULL;
	Node* head = new Node(data[0]);
	Node* pre = head,*p;
	int i;
	for(i = 1;i<n;i++)
	{
		p = new Node(data[i]);
		pre->next = p;
		pre = p;
	}
	return head;
}

void print(Node* head)
{
	while(head)
	{
		cout << head->val << " ";
		head = head->next;
	}
	cout<<endl;
}

void deleteNode(Node* &head)
{
	if(head == NULL)return;
	if(head->next)deleteNode(head->next);
	delete head;
	head = NULL;
}

int main()
{
	int n,i;
	Node* head1,*head2;
	cout << "----------         ---------"<<endl;
	while(cin >> n)
	{
		int* data = new int[n];
		cout <<"-------          ------"<<endl;
		for(i=0;i<n;i++)cin >> data[i];
		head1 = MakeLinkedList(data,n);
		cout <<"-------      -------------"<<endl;
		print(head1);
		cout <<"-------          ------"<<endl;
		for(i = 0;i<n;i++)cin >> data[i];
		head2 = MakeLinkedList(data,n);
		cout <<"-------      -------------"<<endl;
		Node* head = AddLinkList(head1,head2);
		cout <<"-------       -----------"<<endl;
		print(head);
		deleteNode(head1);
		deleteNode(head2);
		deleteNode(head);
		cout << "----------         ---------"<<endl;
	}
	return 0;
}

잘못 이 있 으 면 지적 해 주 십시오. 감사합니다.