문제
비어있지않은 두개의 링크드리스트가 제공되며 이 각각의 링크드리스트에 숫자들은 반대로 저장되어있다.
그리고 각 노드들은 한개의 숫자만 가지고 있다. 각각의 링크드리스트의 노드들을 더한후
링크드리스트로 리턴해라
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int resultCnt = 0;
ListNode dummy,resultNode = new ListNode(0);
dummy = resultNode;
while (l1 != null || l2 != null || resultCnt != 0) {
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
dummy = dummy.next;
resultCnt /= 10;
}
return resultNode.next;
}
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter
|
http://colorscripter.com/info#e" target="_blank" style="text-decoration:none;color:white">cs |
시간복잡도 O(log n)
1. while 셋중에 어느조건이라도 true면 계속 돌아감 , 3개다 false면 멈춤
2. listnode dummy와 resultNode를 생성후 dummy에 resultNode의 인스턴스를 넣어준다.
3. 30번째줄 dummy.next는 resultNode의 next이며 ListNode 인스턴스를 만들어서 넣어줌
4. 31번째줄 dummy에 새롭게 생성된 ListNode 인스턴스를 넣어줌
5. 이런식으로 계속 while문을 돌면서 ListNode안에 ListNode를 생성 하면
따로 resultNode를 건드리지않아도 dummy가 하위 ListNode를 계속 생성을 함.
6. 노드의 숫자는 한자리수만 들어갈수 있기때문에 10으로 나눠서 남은숫자를 next에 집어넣음
7. 10이상일경우 resultCnt에 담김
8. 그럼 null이 아닐경우 resultCnt와 매개변수로 입력받은 l1,l2를 더해줌 그리고 매개변수 l1과 l2는 하위 노드를
넣어서 와일이 돌면서 계속 하위의 노드값을 찾을수있게해줌
9. while 조건이 끝나면 resultNode를 리턴함.
'개발 > algorithm' 카테고리의 다른 글
| leetcode 3번문제 Longest Substring Without Repeating Characters (0) | 2020.04.14 |
|---|---|
| leetcode 445번문제 add two numbers 2 (0) | 2020.04.14 |
| leetcode 653 Two Sum IV - Input is a BST (0) | 2020.04.14 |
| leetcode 167번문제 Two Sum 2 - input array is sorted (0) | 2020.04.14 |
| leetcode 1번문제 Two Sum (0) | 2020.04.14 |