[leet code] Add Two Numbers / JAVA (with chatGPT), 단일 연결 리스트, 얕은 복사

<문제>

두 개의 음수가 아닌 정수를 나타내는 두 개의 비어 있지 않은 연결 목록 이 제공됩니다 . 

숫자는 역순 으로 저장되며 각 노드에는 단일 숫자가 포함됩니다.

두 숫자를 더하고 그 합계를 연결된 목록으로 반환합니다.

숫자 0 자체를 제외하고는 두 숫자의 첫째 자리에 0이 포함되어 있지 않습니다.

 

<예시>
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    	ListNode dummyHead = new ListNode(0); // 더미 헤드 노드
        ListNode p = l1, q = l2, current = dummyHead; // p와 q는 각각 l1과 l2의 현재 노드를 가리킴
        int carry = 0;

        while (p != null || q != null) { // p나 q가 null이 아닐 때 반복
            int x = (p != null) ? p.val : 0; // p가 null이 아니면 p.val, 그렇지 않으면 0
            int y = (q != null) ? q.val : 0; // q가 null이 아니면 q.val, 그렇지 않으면 0
            int sum = carry + x + y; // 현재 자리의 합을 구함
            carry = sum / 10; // carry를 업데이트
            current.next = new ListNode(sum % 10); // 새로운 노드를 결과 리스트에 추가
            current = current.next; // current를 다음 노드로 이동

            if (p != null) p = p.next; // p가 null이 아니면 p를 다음 노드로 이동
            if (q != null) q = q.next; // q가 null이 아니면 q를 다음 노드로 이동
        }

        if (carry > 0) {
            current.next = new ListNode(carry); // 남은 carry를 처리
        }

        return dummyHead.next; // 더미 헤드의 다음 노드를 반환하여 실제 결과 리스트 반환
    }

    public static void main(String[] args) {
        // 예시 입력을 테스트하기 위해 간단한 테스트 케이스를 추가할 수 있습니다.
        ListNode l1 = new ListNode(2);
        l1.next = new ListNode(4);
        l1.next.next = new ListNode(3);
        
        ListNode l2 = new ListNode(5);
        l2.next = new ListNode(6);
        l2.next.next = new ListNode(4);
        
        Solution solution = new Solution();
        ListNode result = solution.addTwoNumbers(l1, l2);
        
        // 결과 출력
        while (result != null) {
            System.out.print(result.val);
            if (result.next != null) {
                System.out.print(" -> ");
            }
            result = result.next;
        }
    }
}

 

1. 변수 선언부에 삼항연산자로 조건을 넣을 수 있다. skrrrrr

 

2. ListNode는 아래와 같이 만들어지기 때문에 l1, l2는 각 연결리스트의 첫번째 노드를 가리키며, while문에 넣고 돌릴때마다 .next로 다음 노드를 지정해줘야 한다.

ListNode l1 = new ListNode(2);
l1.next = new ListNode(4);
l1.next.next = new ListNode(3);

 

 3. current는 dummyhead를 얕은 복사 하므로 current에 추가한 next 노드는 결국 dummyhead에 추가되는 것이다

---

1. 얕은 복사 (Shallow Copy):
   • 얕은 복사는 객체를 복사할 때, 객체의 주소만을 복사하여 두 변수가 같은 객체를 참조하게 합니다.
   • 즉, 복사된 객체와 원본 객체는 같은 메모리를 공유하며, 하위 객체들은 복사되지 않고 원본과 동일한 하위 객체를 참조합니다.
   • 얕은 복사를 수행하는 경우, 원본 객체나 복사본 객체 중 하나를 수정하면 다른 객체도 그 변경사항을 반영합니다.
2. 깊은 복사 (Deep Copy):
   • 깊은 복사는 객체를 복사할 때, 객체의 내용을 재귀적으로 복사하여 두 변수가 서로 다른 객체를 참조하게 합니다.
   • 즉, 복사된 객체와 원본 객체는 서로 다른 메모리를 가지며, 모든 하위 객체들도 새로운 인스턴스를 생성하여 복사됩니다.
   • 깊은 복사를 수행하는 경우, 원본 객체나 복사본 객체 중 하나를 수정해도 다른 객체는 영향을 받지 않습니다.

얕은 복사는 복사 과정에서 하위 객체의 참조만을 복사하므로 복사가 빠르고 메모리 사용량이 적습니다. 하지만 객체 간의 의도하지 않은 연결이 발생할 수 있습니다. 반면에 깊은 복사는 모든 객체를 복사하므로 객체 구조가 복잡할수록 복사에 시간이 오래 걸리고 메모리 사용량도 증가합니다. 하지만 독립적인 객체로써의 완전한 복사를 보장합니다.

---

문제 원문

https://leetcode.com/problems/add-two-numbers/description/

 

참고

• Leetcode - Singly Linked List
• GitHub - SinglyLinkedList