[LeetCode] 0002 - Add Two Numbers

문제

비어 있지 않고 양수인 두 개의 링크드 리스트가 주어진다. 이 숫자들은 역순으로 저장되어 있으며, 하나의 노드에 하나의 숫자가 들어가 있다. 이 두 개의 숫자를 더한 링크드 리스트를 반환하여라. 

풀이

1. 기본적인 접근

먼저 결과 링크드리스트를 만들어 준다. L1, L2의 링크드 리스트의 값을 더하는데 이때 더한 값이 10이 넘어가면 그다음 노드에 넘겨주도록 carry에 값을 할당한다.

노드를 만들어서 현재의 노드 next에 연결해주고 L1, L2이 모두 null이 될 때까지 반복한다.

이 과정이 끝나고 carry값이 있다면 값이 1인 노드를 추가해준다.

결과 반환은 node.next인데 그 이유는 초기 선언 시 0으로 선언하고 next부터 값을 추가했기 때문임.

Time Conplexity(시간 복잡도): O(max(M, N)) - L1, L2 두 링크드 리스트 중 가장 긴 링크드 리스트 만금 시간이 걸림.

Space Conplexity(공간 복잡도) : O(max(M, N)) - 최종적인 결과 링크드리스트의 크기는 max(M,N)+1 임.

2. 재귀적 접근

1번의 풀이를 재귀적 접근으로 풀어본 것으로 시간 복잡도와 공간 복잡도는 1번 풀이와 같다.

Time Conplexity(시간 복잡도): O(max(M,N))

Space Conplexity(공간 복잡도) : O(max(M,N))

 

해당 문제를 풀고자 하시면 이 링크를 누르면 문제를 풀 수 있고, 문제 풀이 코드는 이 링크를 클릭하면 됩니다.