LeetCode - Add Two Numbers

나의 풀이

 

class Solution {
  public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode headNode = new ListNode((l1.val + l2.val) % 10);
    ListNode curNode = headNode;
    int carry = (l1.val + l2.val) / 10;
    l1 = l1.next;
    l2 = l2.next;
    while (Objects.nonNull(l1) || Objects.nonNull(l2)) {
      int firstVal = Objects.nonNull(l1) ? l1.val : 0;
      int secondVal = Objects.nonNull(l2) ? l2.val : 0;
      int totalSum = firstVal + secondVal + carry;
      curNode.next = new ListNode(totalSum % 10);
      curNode = curNode.next;
      carry = totalSum / 10;
      l1 = Objects.nonNull(l1) ? l1.next : l1;
      l2 = Objects.nonNull(l2) ? l2.next : l2;
    }
    if (carry != 0) {
      curNode.next = new ListNode(carry);
    }
    return headNode;
  }
}

 

 

 

떠올린 방식

 

1. convert ListNode to Long, convert Long to ListNode

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
  return convertToNode(convertToLong(l1) + convertToLong(l2));
}

public static long convertToLong(ListNode node) {
  long number = 0L;
  long digit = 1L;
  while (Objects.nonNull(node.next)) {
    number += node.val * digit;
    digit *= 10;
    node = node.next;
  }
  return number + node.val * digit;
}

public static ListNode convertToNode(long num) {
  StringBuilder sb = new StringBuilder();
  sb.append(num);
  int numLen = sb.reverse().length();
  ListNode lastNode = new ListNode(sb.charAt(--numLen) - '0');
  while (numLen > 0) {
    lastNode = new ListNode(sb.charAt(--numLen) - '0', lastNode);
  }
  return lastNode;
}

- time complexity : O(n) , n = 노드 중에 긴 것의 길이

- 한계 : 아래 규칙을 만족하지 못한다. (Long 범위 이상)

 

 

 

2. One by One using carry

- time complexity : O(n)

- logic : carry를 이용해 ListNode 객체를 만들고 이전 ListNode 객체와 이어준다

 

 

결과

 

 

 

---

다른 사람의 풀이

 

1. 솔루션

class Solution {
    // Add Two Numbers (Java improved)
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(0);
        ListNode curr = dummyHead;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0;
            int sum = carry + x + y;
            carry = sum / 10;
            curr.next = new ListNode(sum % 10);
            curr = curr.next;
            if (l1 != null)
                l1 = l1.next;
            if (l2 != null)
                l2 = l2.next;
        }
        return dummyHead.next;
    }
}

• while문 안에 carry != 0이 들어가면서 내 풀이에서 마지막 If문이 필요 없어졌다
• 더미 헤드를 만들어 쓰는 방식도 익숙해져야 하는 듯 하다
• 나는 Objects.nonNull()을 사용했는데, 역시 코딩테스트에서는 직접적으로 null 체크하는 방식이 정석인 듯 하다

 

 

2. 특이한 방식 (재귀 사용)

public ListNode resList = new ListNode(0);
public ListNode head = resList;
public int carry = 0;

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
    int sum = l1.val + l2.val + carry;
    carry  = sum / 10;
    resList.next = new ListNode(sum % 10);
    resList = resList.next;

    if(l1.next != null && l2.next != null)
        addTwoNumbers(l1.next, l2.next);  
    else if (l1.next != null)
        addTwoNumbers(l1.next, new ListNode(0)); 
    else if (l2.next != null)
        addTwoNumbers(new ListNode(0), l2.next);   
    else if (carry > 0)
    {
        resList.next = new ListNode(1);
        resList = resList.next;
    }     
    return head.next;
}

• 아름다운 풀이이다
• 아직 많이 배워야 하는 듯 하다
• 성능 또한 아래의 사진과 같이 좋게 나온다