[Linked List] Add Two Numbers

예시1을 보면 문제 이해가 쉬운데, 두개의 Linked List가 인풋으로 들어오면, 각각 순서를 바꿔서 저장한 후 int로 만들어 이를 더한다. 더한 값을 다시 Linked List로 만드는데, 얘 역시 거꾸로 만든다

 

이 문제는 reverse연산인데, 원래 942+476으로 연산해야 할 input이 거꾸로 들어온다.

그렇다면 들어온 리스트 순서 그대로 연산한다면 어떤 부분을 고려해야 할까?

자릿수대로 더해주고 결과 linked list에 거꾸로 집어넣으면 된다.

그런데 문제는 두 노드의 합이 10이 넘어가는 경우다

10이 넘어가면 1을 다음 자릿수로 넘겨준다.

 

따라서 이 문제의 index는 4개가 필요하다.

List를 만들고 우리는 List.next를 결과로 리턴해줄것이다.

이 List에는 연산값이 담겨져 있어야 한다.

이때 sum은 각 자릿수의 합, carry는 각 자릿수가 10을 넘겼을때 1을 다음 자릿수 연산으로 넘겨주는 역할이다.

 

Linked List에 대해 쭉 Loop를 돌려줄것인데, 이때 각 자릿수의 sum을 더해주고 node를 다음으로 바꿔준다.

주의할점은 sum이 10이 넘으면 carry를 1로 만들어주고, sum에서 1에 해당하는 10을 뺀다.

이후 sum을 리턴할 노드에 박아주고, 다음 sum의 기본값은 1이 있다면 1이 되어야 하므로 carry를 대입해준 후 carry를 초기화시켜준다.

 

이를 도식화시키면 다음과 같다.