Linked List | Merge In Between Linked Lists

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.

 

Medium 난이도의 문제이다. 두 Linked List가 주어졌을 때, list1의 a번부터 b를 삭제한 후, 삭제된 자리에 list2를 넣는 문제이다. O(N)으로 해결하기 위해 아래와 같이 접근했다.

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode temp = null;
        ListNode curr = list1;
        curr = moveNTime(curr, a - 1);
        temp = curr.next;
        
        curr.next = list2;
        
        curr = getLastNode(list2);
        temp = moveNTime(temp, b - a + 1);
        curr.next = temp;
        
        return list1;
    }
    
    private ListNode moveNTime(ListNode node, int n){
        for(int i = 0; i < n; i++){
            node = node.next;
        }
        return node;
    }
    
    private ListNode getLastNode(ListNode node){
        while(node.next != null){
            node = node.next;
        }
        return node;
    }

* Time Complexity: O(M + N), M은 list1의 길이, N은 list2의 길이이다.

* Space Complexity: O(1), 몇개의 노드 포인터만 사용한다.

 

노드를 N번 움직이는 로직이 2번 발생하고, 한 function안에 코드가 길어지는것을 방지하기 위해서 private helper functions를 작성했다. 이 문제에서는, 충분한 길이의 LinkedList를 주었기 때문에, null point exception이 helper methods들에서 발생하지는 않겠지만, 두 메소드를 다른 functions에서 사용한다면, 그점을 보완해주면 좋다.

 

하지만, 위 코드는 최상위 (100%)에 해당하는 Runtime의 솔루션이었다.

만약, helper methods를 다른 장소에서 사용한다면, 아래와 같이 수정할 수 있다.

    private ListNode moveNTime(ListNode node, int n){
        if(node == null){
            return null;
        }
        for(int i = 0; i < n; i++){
            node = node.next;
        }
        return node;
    }
    
    private ListNode getLastNode(ListNode node){
        if(node == null){
            return null;
        }
        while(node.next != null){
            node = node.next;
        }
        return node;
    }

 

null인 노드가 주어졌을 때, null 을 리턴하는식으로 처리해주거나, 또는 exception을 날리던지, -1과 같은 불가능한 값을 가진 노드를 리턴해서 처리하는 식 등 다양한 방법으로 짜볼 수 있을것 같다.

 

 

너무 귀여운 포켓몬 이모티콘,,, 여기서 45번부터 78번 포켓몬까지 빼고 아래 2세대 포켓몬으로 넣는다면? 위에 짜둔 알고리즘을 사용하면, 78 + 99, 총 177번의 loop을 지나서 완성시킬 수 있다!

1세대 관동지방 포켓몬들

 

 

Reference

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

Merge In Between Linked Lists - LeetCode

https://m.blog.naver.com/hanee218/221242240610

포켓몬스터 2세대 포켓몬 도감 - 성도지방 성도도감