[ Leetcode ] 1669. Merge In Between Linked Lists - Java

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 1:

 
 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.
 

Example 2:

 
 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

 

Solution

 

 
 import java.util.*;
 class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        List<Integer> list = getValueList(list1);
        
        int end = list.get(list.size()-1);
        ListNode answer = new ListNode(list.get(end));
        for(int i=end-1; i> b; i--){
            answer = new ListNode(list.get(i), answer);
        }    
        
        int max = getMax(list2);
        for(int i=max; i>= 1000000; i--){
            answer = new ListNode(i, answer);
        }
        
        for(int i=a-1; i >= 0; i--){
            answer = new ListNode(list.get(i), answer);
        }
        
        return answer;
    }
    public int getMax(ListNode list){
        int max = 0;
        while(list != null){
            if(list.next == null){
                max = list.val;
            }
            list = list.next;
        }
        return max;
    }
    public List<Integer> getValueList(ListNode list){
        List<Integer> arrList = new ArrayList<>();
        while(list != null){
            arrList.add(list.val);
            list = list.next;
        }
        return arrList;
    }
 }
 

1. ListNode 값을 ArrayList에 담는다

2. 마지막 값에서 b번째 전까지의 값으로 ListNode를 만들다

3. 껴넣을 ListNode도 마지막 값부터 ListNode로 만들어준다 -> 이부분을 한번에 하면 좋을것같은데 아직 모르겠다

4. 남은 0번째부터 a번째까지의 값도 ListNode로 만든다

 

너무 느리다 방법 다시 찾기 (++추가!)

 

++ 앞뒤 ListNode를 구분지어보기로 한다

 

public class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {

        ListNode temp = new ListNode(0);
        temp.next = list1;
        ListNode front = temp;
        ListNode back = temp;

        for(int i = 0; i < a; i++){
            front = front.next;
        }
        front.next = list2;
        
        while(list2.next != null){
            list2 = list2.next;
        }
        for(int i = 0; i <= b; i++){
            back = back.next;
        }
        list2.next = back.next;

        return temp.next;
    }   
 }
 

1. 시작 노드부터 next로 a번째까지 간 뒤 머지할 list2를 넣어준다

2. list2도 계속 뒤로뒤로 해서 끝까지 간다

3. 시작 노드부터 next로 b번째까지 간 뒤 list2 뒤에 붙여준다

4. list1을 시작한 temp.next를 return 한다

 

100%!!!

근데 여전히 헷갈리는 중..... 비슷한 문제를 좀 더 풀어봐야겠다