[LeetCode] Merge Two Sorted Lists

Problem: Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example:

Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Input: list1 = [], list2 = []
Output: []

Input: list1 = [], list2 = [0]
Output: [0]

Approach: We have already done it recursively before. Just adding the iterative approach here. You can just understand it by looking at the implementation.

Implementation in C#:

    public ListNode MergeTwoLists(ListNode list1, ListNode list2)

    {

        var itr1 = list1;

        var itr2 = list2;

        var head = new ListNode();

        var itr = head;

        while (itr1 != null && itr2 != null)

        {

            if (itr1.val <= itr2.val)

            {

                itr.next = itr1;

                itr1 = itr1.next;

            }

            else

            {

                itr.next = itr2;

                itr2 = itr2.next;

            }

            itr = itr.next;

        }

        if (itr1 != null)

        {

            itr.next = itr1;

        }

        else if (itr2 != null)

        {

            itr.next = itr2;

        }

        return head.next;

    }

Complexity: O(Max(m, n))

Middle of the Linked List

Problem: Given the head of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

Example:

Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.

Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.

Approach: We can do it in two passes where in first iteration we can get the number of nodes and in the second iteration we will get the size/2th node. 

Let's try to reduce the number of iterations. What we can do, we can use two pointers; one is slow which goes 1 step at one time and one is fast which goes 2 steps at a time:

• slow = slow.next
• fast = fast.next.next

Obviously when fast is null or it's next is null, slow will be pointing at the middle node. That's all!

Implementation in C#:

    public ListNode MiddleNode(ListNode head)

    {

        if (head == null || head.next == null)

        {

            return head;

        }

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null)

        {

            slow = slow.next;

            fast = fast.next.next;

        }

        return slow;

    }

Complexity: O(n)

[InterviewBit] Subarray with given XOR

Problem: Given an array of integers A and an integer B.

Find the total number of subarrays having bitwise XOR of all elements equals to B.

Example:

Input 1:

 A = [4, 2, 2, 6, 4]
 B = 6

Input 2:

 A = [5, 6, 7, 8, 9]
 B = 5

Example Output

Output 1:

 4

Output 2:

 2

Example Explanation

Explanation 1:

 The subarrays having XOR of their elements as 6 are:
 [4, 2], [4, 2, 2, 6, 4], [2, 2, 6], [6]

Explanation 2:

 The subarrays having XOR of their elements as 5 are [5] and [5, 6, 7, 8, 9]

Approach: We will use hash map to solve this problem. Approach is simple, we will keep doing the xor of every element and store each xor and its frequency in the hashmap. Now at every step we just need to check if curr_xor ^ B exist in the map or not, if yes we will just add count of curr_xor ^ B to the result. That's all!

Implementation in C#:

    public int solve(List<int> A, int B) 

    {

        int length = A?.Count ?? 0;

        if (length == 0)

        {

            return 0;

        }

        var xorMap = new Dictionary<int, int>();

        int xor = 0;

        int count = 0;

        xorMap[xor] = 1;

        for (int i = 0; i < length; ++i)

        {

            xor ^= A[i];

            if (xorMap.ContainsKey(B ^ xor))

            {

                count += xorMap[B ^ xor];

            }

            if (!xorMap.ContainsKey(xor))

            {

                xorMap[xor] = 0;

            }

            ++xorMap[xor];

        }

        return count;

    }

Complexity: O(n)