난이도 : medium
- 두개의 링크드 리스트가 주어짐
- 음이 아닌 정수로 이루어짐
- 각 링크드 리스트는 역순으로 데이터가 표현됨
- 0을 시작으로 하는 데이터는 존재하지 않음
- 두개의 링크드 리스트 합을 표현한 링크드리스트를 리턴하라
- 링크드리스트의 길이 : 1~100
1. 접근법
- l1과 l2의 next가 null이 될 때까지 반복
- next에 새로운 노드를 붙임
- 반복 횟수별 노드를 생성하여 val값을 합으로 만듬
2. 의사코드
int carry = 0;
ListNode ans = new ListNode();
int sum = 0;
while (l1 혹은 l2이 null이 아니면) {
ans.val = l1.val + l2.val + carry;
if (ans.val >= 10) {
ans.val -= 10;
carry 증가;
} else {
carry = 0;
}
ans.next = new ListNode();
l1 = l1.next;
l2 = l2.next;
}
3. 구현 코드
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int l1Val = 0;
int l2Val = 0;
int carry = 0;
ListNode ans = new ListNode();
ListNode head = ans;
ListNode before = ans;
ListNode tail = ans;
while (l1 != null || l2 != null) {
l1Val = l1 == null ? 0 : l1.val;
l2Val = l2 == null ? 0 : l2.val;
ans.val = l1Val + l2Val + carry;
if (ans.val >= 10) {
ans.val -= 10;
carry = 1;
} else {
carry = 0;
}
ans.next = new ListNode();
l1 = l1 == null ? null : l1.next;
l2 = l2 == null ? null : l2.next;
before = ans;
ans = ans.next;
tail = ans;
}
if (carry == 1) {
tail.val = carry;
} else {
before.next = null;
}
return head;
}
}
- 반복할때마다 ans의 next에 새로운 노드를 생성한다
- carry가 있다면 tail 노드 값을 carry로 할당
- carry가 없다면 tail 노드를 삭제해야 함
- 삭제하기 위해 tail노드의 직전 노드인 before를 변수로 선언
- 반복문을 돌때마다 값을 갱신해줌
- before 노드의 next를 null 할당
- 삭제하기 위해 tail노드의 직전 노드인 before를 변수로 선언
4. 시간복잡도, 공간복잡도 예상
- 시간복잡도 : O(n) - n개의 원소를 반복하므로
- 공간복잡도 : O(1) - 반복문 안에서 선언되는 변수는 없으므로 상수값만 메모리에 잡힘
5. 개선점
모르겠다
6. 회고
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode dummy_head = new ListNode(0);
ListNode l3 = dummy_head;
int carry = 0;
while (l1 != null || l2 != null) {
int l1_val = (l1 != null) ? l1.val : 0;
int l2_val = (l2 != null) ? l2.val : 0;
int current_sum = l1_val + l2_val + carry;
carry = current_sum / 10;
int last_digit = current_sum % 10;
ListNode new_node = new ListNode(last_digit);
l3.next = new_node;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
l3 = l3.next;
}
if (carry > 0) {
ListNode new_node = new ListNode(carry);
l3.next = new_node;
l3 = l3.next;
}
return dummy_head.next;
}
}
(출처 : NickWihte youtube)
- carry를 10의 몫으로 표현
- 현재 노드의 값을 10의 나머지 연산으로 표현
- 반복문을 도는중에 새로운 노드를 생성하고 한칸씩 이동하게 될 경우, 마지막 노드를 지워주어야 하는 상황이 생김
- dummy node를 생성한 후, dummy node의 next로 이동시키면서 생성
- carry가 존재할 경우만 뒤에 carry값을 가진 새로운 노드를 붙임
- dummy node의 next를 반환
공간복잡도를 아낄 수 있음
가독성과 응집도가 올라간다
'Algorithm > (Java) PS' 카테고리의 다른 글
[Leetcode Top Interview 150] 150. Evaluate Reverse Polish Notation (0) | 2023.09.01 |
---|---|
[Leetcode Top Interview 150] 155. Min Stack (0) | 2023.08.31 |
[Leetcode Top Interview 150] 141. Linked List Cycle (0) | 2023.08.28 |
[Leetcode Top Interview 150] 3. Longest Substring Without Repeating Characters (0) | 2023.08.28 |
[Leetcode Top Interview 150] 209. Minimum Size Subarray Sum (0) | 2023.08.28 |