LeetCode 1669번: Merge In Between Linked Lists(Python3)

https://leetcode.com/problems/merge-in-between-linked-lists/

Merge In Between Linked Lists - LeetCode

해당 문제는 위 링크를 클릭하면 볼 수 있다.

 

문제 설명

1) 사이즈가 n인 list1과 사이즈가 m인 list2가 주어진다.

2) list1의 a번째 node부터 list1의 b번째 node까지를 제거한다.

3) list1의 a-1번째 node 이후에는 list2가 이어지고, list2가 마지막에 도달하면 list1의 b+1 노드와 연결시킨다.

Example

Input: list1 = [0,1,2,3,4,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]

Output: [0,1,2,1000000,1000001,1000002,5]

 

풀이에서 사용한 자료구조

Linked List

    - element 간의 연결(link)를 이용해서 리스트를 구현한 것을 의미한다.

    - 자료의 추가와 삭제에 O(1)이라는 짧은 시간이 걸리나, 데이터를 찾는 과정에서는 O(n)의 시간이 걸린다

 

문제 풀이법

1. list 1의 노드 개수를 count 변수로 확인하며, count+1이 a가 되면, b까지를 remove 하고, list2와 연결한다.

2. list 2가 끝이 나면, 이를 다시 list1의 b+1과 연결 시킨다.

 

Source Code

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
  def mergeInBetween(self, list1: ListNode, a: int, b: int, list2: ListNode) -> ListNode:
        headfirst=list1
        headlast=list2
        count=0
        while count!=b:
            if count+1==a:
                x=headfirst
            headfirst=headfirst.next
            count=count+1
        y=headfirst 
        x.next=headlast
        while headlast.next!=None:
            headlast=headlast.next
        headlast.next=y.next
        return list1

 

결과

결론

링크드 리스트를 연결하고 끊어내는 문제였으며, 기초적인 자료 구조에 대한 이해를 키울 수 있었다.

시간 복잡도: O(n+m) : list1과 list2를 완전탐색하므로 둘의 크기의 합이 시간 복잡도라고 할 수 있다.