[각종 면접 문제] 등 장 체인 폼 스 캔

등 장 체인 폼 스 캔 구 화
두 개의 단일 체인 시트 (singly linked list) 는 각 노드 에 0 - 9 의 숫자 를 입력 하면 두 개의 대수 에 해당 합 니 다.그리고 이 두 수의 합 (새 list) 을 되 돌려 줍 니 다.이 두 입력 의 list 길 이 는 같다.요 구 는:
재 귀 할 필요 없어.
요구 알고리즘 은 가장 좋 은 상황 에서 두 개의 list 를 한 번 만 옮 겨 다 니 고 최 악의 경우 두 번 만 옮 겨 다 닙 니 다
아래 의 이 방법 도 보기 만 해도 아름 다 울 뿐, 사실은 한 번 훑 어 본 것 도 아니 고, 앞 뒤 두 개의 바늘 도 두 번 훑 어 본 것 도 아니 잖 아.그래서 저 는 결과 링크 를 만 들 고 역 치 한 다음 에 진 위 를 처리 하고 역 치 하 는 경향 이 있 습 니 다.
두 개의 입력 링크 를 한 번 만 옮 겨 다 닐 수 있 으 니 높 은 자리 에서 시작 합 시다.이런 제한 조건 하에 서 이것 이 유일한 길이 다.그래서?진 위 는 어떻게 정 합 니까?먼저 높 은 자 리 를 올 리 고 낮은 자 리 를 더 하면 낮은 위치 에서 발생 하 는 진 위 는 어떻게 높 은 위치 로 올 립 니까?우리 앞 방향 지침 없어.앞 방향 지침 이 없 는 이상 우 리 는 임시 지침 으로 높 은 위 치 를 가리 키 게 하고 낮은 위치 에 진 위 를 더 할 때 우 리 는 높 은 위 치 를 조작 할 수 있다.그림 을 보 여 주세요.

    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<vector>
#include<string>
using namespace std;

struct ListNode
{
	int val;
	ListNode* next;
	ListNode(int v):val(v),next(NULL){}
};

ListNode* addTwo(ListNode* l1,ListNode* l2)
{
	ListNode guard(-1);
	ListNode* pNine=NULL,*tail=&guard;
	while(l1&&l2)
	{
		ListNode* tmp=new ListNode(l1->val+l2->val);
		tail->next=tmp;
		tail=tail->next;
		if(tmp->val>=10)
		{
			if(pNine==NULL)
			{
				ListNode* head=new ListNode(0);
				head->next=guard.next;
				guard.next=head;
				pNine=head;
			}
			pNine->val++;
			pNine=pNine->next;
			while(pNine!=tmp)
			{
				pNine->val=0;
				pNine=pNine->next;
			}
			tmp->val=0;
			pNine=tmp;
		}
		else if(tmp->val<9)
		{
			pNine=tmp;
		}
		l1=l1->next,l2=l2->next;
	}
	return guard.next;
}
ListNode* create(int n)
{
	ListNode head(-1);
	ListNode* tail=&head;
	while(n--)
	{
		tail->next=new ListNode(0);
		cin>>tail->next->val;
		tail=tail->next;
	}
	return head.next;
}
int main()
{
	while(1)
	{
		int n;
		cin>>n;
		ListNode* l1=create(n);
		ListNode* l2=create(n);
		ListNode* res=addTwo(l1,l2);
		cout<<endl;
	}
}