[LeetCode- Ch5. 연결 리스트] 1. 두 숫자 더하기

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

Add Two Numbers - LeetCode

 

1. 노드의 구성요소 : 값과 다음 노드

2. 널이 아니면 반복해서 연결한다.

-> 합이 일의자리가 넘어갈 때 사용하는 변수 carry

 

/**
 * 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; }
 * }
 */

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode node = solve(l1,l2);
// 		while(node!=null) {
// 			System.out.println(node.val);
// 			node =node.next; //node에 next를 지정해야 반복 가능
// 		}
        return node;
    }
    public static ListNode solve(ListNode l1, ListNode l2) {
		//1. ds
		
		// 값이 0인 더미 데이터 생성
		ListNode newHead = new ListNode(0);
		
		//l1, l2 카피하고, newHead 생성 -> 일반적으로 카피해서 사용
		ListNode p1=l1, p2=l2, p3=newHead;	
		
		//합이 일의 자리가 넘어갈 때, 필요한 변수 생성
		int carry=0;
		
		//2. for, while
		while(p1!=null||p2!=null) {	//p1과 p2가 널이 탈출조건
			if(p1 !=null) {
				carry += p1.val;	//p1 : 2,4,3 -> carry에 2 담는다.
				p1=p1.next;		//p1.next가 4로 넘어가므로 -> 2, next를 날리고 4, next가 p1			
			}
			if(p2 !=null) {
				carry += p2.val;	//p2 : 5,6,2 -> carry에 5 담는다.
				p2=p2.next;		//p2.next가 6으로 넘어가므로 -> 5, next를 날리고 5, next가 p2
			}
			//carry에 p1과 p2의 합이 담겨져 있다. -> p3를 만들어 담기
			p3.next = new ListNode(carry%10);	//일의자리로만 저장이 가능하므로 몫을 저장하고, 나머지를 뒤로 보낸다.
			p3 =p3.next;	//7,next에서 0,next으로 넘어가기 위해
			//4+6이 10인데, 1을 올려주기위해
			carry /=10;		//carry에 몫을 넘긴다.
			
			
		}
		//마지막 자리에서도 일의 자리를 초과할 수 있기 ��문에 -> 생성
		if(carry==1) p3.next=new ListNode(1);
		
		return newHead.next;	//넘길 때 더미데이터를 제외한 나머지데이터만
	}
}