Algorithm

[LeetCode] 2816. Double a Number Represented as a Linked List (Daily Question)

SeangG 2024. 5. 7. 10:15

문제


You are given the head of a non-empty linked list representing a non-negative integer without leading zeroes.

Return the head of the linked list after doubling it.

 

연결 리스트의 head가 주어졌을 때 쭉 이어서 만든 숫자의 두배를 만드는 만드는 문제이다.

[1, 2, 3]이 주어졌을 때 123 * 2 => 246 => [2, 4, 6]의 과정을 거친다.

연결 리스트는 객체 형식으로 주어지고 값을 의미하는 node.val, 다음 노드를 가리키는 node.next이 맴버변수로 존재한다.

 

Example 1:

Input: head = [1,8,9]
Output: [3,7,8]
Explanation: The figure above corresponds to the given linked list which represents the number 189. Hence, the returned linked list represents the number 189 * 2 = 378.

Example 2:

Input: head = [9,9,9]
Output: [1,9,9,8]
Explanation: The figure above corresponds to the given linked list which represents the number 999. Hence, the returned linked list reprersents the number 999 * 2 = 1998.

 

풀이


아이디어

- node.val의 범위가 0~9이므로 두배를 했을 때 앞 노드에 1을 더하는 것 외에는 다른 영향을 주지 못한다.

- head부터 순차적으로 탐색하며 node.next.val>=5일때 node.val에 1을 더해준다.

 

 

코드

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def doubleIt(self, head: Optional[ListNode]) -> Optional[ListNode]:
        node = head
        if head.val >= 5:
            head = ListNode(1, head)
            node = head.next

        while node:
            node.val = node.val*2%10
            if node.next and node.next.val>=5: node.val += 1
            node = node.next

        return head

 


 

후기


각 노드가 다른 노드에 어떤 영향을 주는 지 잘 생각해 본다면 쉽게 풀 수 있는 문제였다.

깊이 생각하지 않았다면 node.val을 전부 꺼내서 두배로 만들고 새로운 연결리스트를 만드는 비효율적인 방법을 사용했을 것이다.

 

예외사항으로는 head 노드가 5 이상일 때 새로운 head 노드를 생성해야 한다는 것인데, 크게 어렵지는 않다.