LeetCode/2. Add Two Numbers

342라는 숫자가 있으면 1의 자리부터 해서 노드가 2->4->3 으로 연결되어 있다. 주어진 두 개의 노드를 1의 자리부터 편안하게 더해가면 된다. leading zero도 없다고 하니 신경쓸 필요 없이 더하면 된다.

다만, 문제의 함정은 두 리스트의 길이가 항상 같지는 않다는 것. 그러면 2가지 케이스로 나뉜다.

1. 두 리스트의 길이가 같을때
    한 쪽의 next 포인터가 nullptr이 아닐때까지 계속 이동하면서 더하면 된다.

2. 두 리스트의 길이가 다를때
    1번의 방법을 이용한 후에 남은 쪽을 쭉 붙여주면 된다.

먼저 while문으로 두 녀석의 합을 구해서 쭉 붙인다. up은 이전 자리수의 합이 10이 넘을 경우 true가 된다. 처음에는 false로 초기화

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        ListNode* ret = new ListNode;
        ListNode* cur = ret;
        bool up=false;
        //둘 다 아직 끝이 아닐경우
        while(true)
        {
            int sum = l1->val + l2->val;
            
            if(up)
            {
                sum+=1;
                up=false;

            }
            
            if(sum>=10)
            {
                up=true;
                sum%=10;
            }
            
            cur->val = sum;            
            
            if(l1->next == nullptr || l2->next == nullptr)
                break;
            
            l1 = l1->next;
            l2 = l2->next;
            
            ListNode* nextNode = new ListNode;
            cur->next = nextNode;
            cur = nextNode;
        }

 

이후 어느 한 쪽이 살아있는지 판단한다.

//한 쪽만 살아 있는 경우
        if(l1->next!=nullptr && l2->next==nullptr)
        {
            while(l1->next!=nullptr)
            {
                l1 = l1->next;
                ListNode* nextNode= new ListNode;
                cur->next = nextNode;
                cur = nextNode;
                if(up)
                {
                    cur->val = l1->val + 1;
                    if(cur->val >= 10)
                    {
                        cur->val %=10;
                        up = true;
                    }
                    else
                    {
                        up = false;
                    }
                }
                else
                {
                    cur->val = l1->val;
                }
            }
        }
        else if(l1->next==nullptr && l2->next!=nullptr)
        {
            while(l2->next!=nullptr)
            {
                l2 = l2->next;
                ListNode* nextNode= new ListNode;
                cur->next = nextNode;
                cur = nextNode;
                cur->val = l2->val;
                if(up)
                {
                    cur->val += 1;
                    if(cur->val>=10)
                    {
                        cur->val %= 10;
                        up = true;
                    }
                    else
                    {
                        up = false;
                    }
                }
            }
        }

이제 한 단계만 더 하면 된다. 바로 999999와 1을 더하는 경우에는 한 쪽이 끝난 후에도 계속해서 up이 true가 되어 마지막에는 10000000이 된다. 즉, 자리수가 바뀐다. 마지막에도 up이 true인지 확인하는 작업을 한다.

        if(up)
        {
            ListNode* nextNode = new ListNode;
            nextNode->val = 1;
            cur->next = nextNode;
            cur = nextNode;
        }
        
        return ret;
    }

위의 3단계를 이어서 복붙하면 코드 완성이다.