[Leetcode Top Interview 150] 2. Add Two Numbers

난이도 : 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 할당

 

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를 반환

 

공간복잡도를 아낄 수 있음

가독성과 응집도가 올라간다