문제
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 노드를 생성해야 한다는 것인데, 크게 어렵지는 않다.