1. 문제
leetcode 2. Add two numbers
역순으로 연결된 두 리스트의 합을 구하여라.
2. 내 풀이
먼저 각 리스트 노드의 값을 가져올 포인터 l1, l2를 만든다. 그리고 l1, l2 뒤의 노드를 가리킬 p1, p2, 올릴 수를 저장할 carry 변수를 만든다. 그리고 l1, l2가 존재할 동안 탐색을 진행한다. 탐색에서는 l1, l2의 값과 carry를 더해 sum 변수에 저장한다. sum의 10의자리수는 carry에 저장해 올리고, 1의자리수는 l1, l2에 모두 저장한다. 그리고 l1이나 l2 중 하나만 남아있다면 carry와 남아있는 리스트의 값만 더해서 sum과 carry를 구한다. 마지막으로 리스트의 모든 노드를 더했는데 carry가 남아있다면 새 노드를 만들어 해당 carry를 저장하고 답을 저장한 리스트의 마지막에 연결한다. 그리고 답을 저장한 리스트의 첫번째 노드를 리턴한다.
3. 모범 답안
책에 나와 있는 풀이는 유사한 알고리즘을 사용했지만 결과를 저장하기 위한 연결리스트를 새로 만들었다. 그리고 list1, list2, 올림 해야할 값인 carry 중 하나라도 있는 동안 노드 생성을 진행한다. 먼저 list1.val, list2.val, carry를 더해서 sum을 구한다. 그리고 이 sum을 이용해 올림할 carry와 합을 10으로 나눈 나머지인 val을 구한다. 그리고 head.next에 val을 넣고 head를 한칸 앞으로 올리며 노드 생성을 마무리 한다.
