1669-kir3i.md

1669. Merge In Between Linked Lists

Solution

• 시간복잡도: O(N+M)

• 알고리즘

  자료구조

• 풀이설명

  list1에서 삭제할 노드의 바로 전 노드(idxS)와 바로 뒤 노드(idxE)를 미리 구해두고 list2에 연결하면 됩니다.

• 소스코드

  • C++

    class Solution {
    public:
        ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
            ListNode *p = list1, *idxS, *idxE;
            for(int i=0; i<a-1; i++)
                p = p->next;
            idxS = p;	// list1[a-1]
            
            for(int i=0; i<b-a+2; i++)
                p = p->next;
            idxE = p;	// list1[b+1]
            
            idxS->next = list2;
            
            while(list2->next)
                list2 = list2->next;
            list2->next = idxE;
            
            return list1;
        }
    };

  • Python

    class Solution:
        def mergeInBetween(self, list1, a, b, list2):
            p = list1
            for _ in range(a-1):
                p = p.next
            idxS = p    # list1[a-1]
    
            for _ in range(b-a+2):
                p = p.next
            idxE = p    # list1[b+1]
    
            idxS.next = list2
    
            while list2.next:
                list2 = list2.next
            list2.next = idxE
    
            return list1