링크 : https://leetcode.com/problems/can-place-flowers/

description

You are given two linked lists: list1 and list2 of sizes n and m respectively. Remove list1’s nodes from the ath node to the bth node, and put list2 in their place.

The blue edges and nodes in the following figure incidate the result: Build the result list and return its head.

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]
Explanation: We remove the nodes 3 and 4 and put the entire list2 in their place. The blue edges and nodes in the above figure indicate the result.

Input: list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
Output: [0,1,1000000,1000001,1000002,1000003,1000004,6]
Explanation: The blue edges and nodes in the above figure indicate the result.

Constraints

• 3 <= list1.length <= 104
• 1 <= a <= b < list1.length - 1
• 1 <= list2.length <= 104

풀이

코드

# 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:
        head = list1
        start = list1
        end = list1
        
        while end.val != b  :
            if start.val != a-1 : start = start.next
            end = end.next
        
        start.next = list2
        while start.next : start = start.next
        start.next = end.next
        
        return head

결과

Runtime: 432 ms, faster than 93.00% of Python3 online submissions
Memory Usage: 20.2 MB, less than 24.23% of Python3 online submissions

설명

start는 제거하는 리스트를 가리키고 있는 노드이다. 즉 a-1을 값으로 가지는 노드다. end는 제거해야 할 리스트의 마지막 노드이다. end는 start와 같거나 나중에 나오는 노드이므로 end를 기준으로 while문을 돌린다.

그렇게 두 노드를 찾고 나면 start의 next는 a 노드가 아닌, list2의 맨 앞 노드가 된다. 그리고 list2를 끝까지 순회한 다음 마지막 노드의 next는 end의 next가 된다. 맨 처음 저장해둔 list1의 head를 리턴해주면 된다.