Solved! Leetcode 1669. Merge In Between Linked Lists

Merge In Between Linked Lists

Description

You are given two linked lists: list1 and list2 of sizes n and m respectively.

Remove list1‘s nodes from the a^th node to the b^th 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.

Example 1

<strong>Input:</strong> list1 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]
<strong>Output:</strong> [10,1,13,1000000,1000001,1000002,5]
<strong>Explanation:</strong> 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 = [10,1,13,6,9,5], a = 3, b = 4, list2 = [1000000,1000001,1000002]

Output: [10,1,13,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

<strong>Input:</strong> list1 = [0,1,2,3,4,5,6], a = 2, b = 5, list2 = [1000000,1000001,1000002,1000003,1000004]
<strong>Output:</strong> [0,1,1000000,1000001,1000002,1000003,1000004,6]
<strong>Explanation:</strong> 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 <= 10⁴
1 <= a <= b < list1.length - 1
1 <= list2.length <= 10⁴

Approach

Get tail of list 2
Get node a-1 and b+1
Merge two lists by pointing list1 a-1.next to the head of list 2 and pointing the tail.next of list 2 to b+1 node of list 1

Solution

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

        //1.get tail of list 2
        ListNode t2 = getTail(list2);
        //2. get node a-1 and b+1
        ListNode aPrev = getPrevNode(list1, a);
        ListNode bNext = aPrev.next;
        int diff = b-a;
        int i=0;
        while(i<diff && bNext!=null){
            bNext = bNext.next;
            i++;
        }
        //3. Merge two lists by pointing list1 a-1.next to the head of list 2 and pointing the tail.next of list 2 to b+1 node of list 1
        aPrev.next = list2;
        t2.next = bNext.next;
        return list1;
    }

    private ListNode getTail(ListNode l){
        while(l.next!=null){
            l = l.next;
        }
        return l;
    }

    private ListNode getPrevNode(ListNode l, int a){
        ListNode prev = null;
        int i=0;
        while(l!=null && i!=a){
            prev = l;
            l = l.next;
            i++;
        }

        return prev;
    }
}

class Solution {

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

//1.get tail of list 2

ListNode t2 = getTail(list2);

//2. get node a-1 and b+1

ListNode aPrev = getPrevNode(list1, a);

ListNode bNext = aPrev.next;

int diff = b-a;

int i=0;

while(i<diff && bNext!=null){

bNext = bNext.next;

i++;

}

//3. Merge two lists by pointing list1 a-1.next to the head of list 2 and pointing the tail.next of list 2 to b+1 node of list 1

aPrev.next = list2;

t2.next = bNext.next;

return list1;

}

private ListNode getTail(ListNode l){

while(l.next!=null){

l = l.next;

}

return l;

}

private ListNode getPrevNode(ListNode l, int a){

ListNode prev = null;

int i=0;

while(l!=null && i!=a){

prev = l;

l = l.next;

i++;

}

return prev;

}

Rate this post

Coddicted