오늘 뭐 개발하지?

문제 링크 : leetcode.com/problems/reverse-linked-list/

이 문제는 linked list를 역순으로 반환하는 문제이다.

풀이방법

새로운 linked list를 만들고, 입력받은 linked list를 탐색하면서 새로운 linked list를 역순으로 연결되도록 하였다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None # 첫 Linked List 생성
        # head List의 끝까지 탐색
        while head:
            temp = ListNode()
            temp.val = head.val
            temp.next = prev
            prev = temp
            head = head.next
        return prev

문제 링크 : https://leetcode.com/problems/merge-two-sorted-lists/

이 문제는 정렬된 두 개의 linked list를 merge하여 정렬된 linked list를 반환하는 문제이다.

풀이방법

두 리스트가 이미 정렬이 되어있기 때문에 merge sort와 같은 방법으로 풀었다.

두 리스트 중 작은 쪽을 merge_list에 복사하는 작업을 반복하여 merge_list를 반환하였다.

l1, l2 리스트의 연결 자체를 바꾸는 방법도 가능할 것 같은데 새로운 merge_list를 만드는 쪽이 더 쉽고 직관적이어서 다음과 같이 풀이하였다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
        # 둘 다 빈 리스트일 때
        if not l1 and not l2:
            return None
        merge_list = ListNode()
        # curr = 현재 List 위치
        curr = merge_list
        while l1 or l2:
            if not l1:
                curr.val = l2.val
                l2 = l2.next
            elif not l2:
                curr.val = l1.val
                l1 = l1.next
            elif l1.val > l2.val:
                curr.val = l2.val
                l2 = l2.next
            elif l1.val <= l2.val:
                curr.val = l1.val
                l1 = l1.next
            if l1 or l2:
                curr.next = ListNode()
                curr = curr.next
        return merge_list

문제 링크 : https://leetcode.com/problems/palindrome-linked-list/

이 문제는 linked list가 주어졌을 때, 해당 list가 팰린드롬인지 확인하는 문제이다.

풀이방법

해당 list가 팰린드롬인지 아닌지 T/F를 판단하는 문제이기 때문에 linked list의 value를 새로운 list를 만들어서 저장 후 팰린드롬인지 확인하였다.

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        val_list = []
        curr = head
        while curr:
            val_list.append(curr.val)
            curr = curr.next
        return val_list == val_list[::-1]