[LeetCode] 1669. Merge In Between Linked Lists

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

Leetcode - Merge In Between Linked Lists

문제 유형 : 연결 리스트

문제 난이도 : Medium

 

문제

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 indicate the result:

Build the result list and return its head.

 

당신은 list1과 list2의 두 연결리스트를 받습니다.

list1의 a번째노드에서 b번째노드를 없애고, 대신 list2로 대체하세요.

 

풀이

우선, b-a+1만큼 먼저 포인터를 하나 보낸다.

그 뒤, 포인터를 하나 더 만들어서 둘다 a-1만큼 보낸다.

이러면 각각 a-1과 b번째에 위치한다.

 

a-1에서 list2의 head에 연결시키고, tail로 이동해서 b의 next로 연결시킨다.

 

코드

C++

#pragma GCC optimize("03", "unroll-loops");

static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {
        auto left = list1;
        auto right = list1;

        for(int i = 0; i < b-a+1; i++) {
            right = right -> next;
        }

        for(int i = 0; i < a-1; i++) {
            right = right -> next;
            left = left -> next;
        }

        left -> next = list2;
        
        while(left -> next != NULL) {
            left = left -> next;
        }

        left -> next = right -> next;

        return list1;
    }
};