✅Easy✨ ||C++|| Beats 100% || With Explanation||
Intuition\n Describe your first thoughts on how to solve this problem. \nThe intuition of code is to merge two singly linked lists by replacing a segment of the
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe intuition of code is to merge two singly linked lists by replacing a segment of the first list (from position a to b) with the entire second list. The approach involves three main steps: finding the node just before the start of the segment to be replaced in the first list, finding the node just after the end of this segment, and finally linking the second list between these two nodes. The last part of the process connects the end of the second list to the node just after the segment in the first list. This operation effectively splices the second list into the first, between the positions a and b, inclusive.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Initialize Pointers and Counter: The solution starts by initializing a pointer point1 to the start of list1 and a counter variable count to 1. This setup prepares for traversal through the list.\n\n2. Traverse to the a-1th Node: The loop continues until point1 points to the node just before the ath node (1-indexed) or the a-1th node (0-indexed). This is the node after which list2 will be inserted.\n\n3. Traverse to the b+1th Node: A second pointer point2 starts at the node immediately after point1 and moves forward until it points to the node just after the bth node. This node will be the point where list1 continues after list2 has been inserted.\n\n4. Insert list2 Between a and b: The next pointer of the node at a-1 is updated to point to the start of list2. This effectively inserts list2 at position a.\n\n5. Find the End of list2: A temporary pointer traverses list2 to find its last node. This step is necessary to link the end of list2 back to list1.\n\n6. Link the End of list2 to list1: The next pointer of the last node in list2 is updated to point to point2, the b+1th node of list1. This completes the insertion process.\n\n7. Return list1: The function returns the head of the modified list1, which now includes list2 between the ath and bth positions.\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n The algorithm traverses each list at most once. The traversal of list1 to positions a and b takes (O(b)) time, as it stops after reaching the b+1th node. The traversal of list2 to find its end takes (O(n)) time, where (n) is the length of list2. Thus, the total time complexity is (O(b + n)), where (b) is the position in list1 where the merge ends, and (n) is the length of list2.\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nThe algorithm uses a constant amount of extra space for pointers and the counter variable, so the space complexity is (O(1)). Note that the space used by the lists themselves is not considered part of the space complexity for this analysis, as it is not additional space allocated by the algorithm.\n# Code\n```\n/**\n * Definition for singly-linked list.\n * struct ListNode {\n *     int val;\n *     ListNode *next;\n *     ListNode() : val(0), next(nullptr) {}\n *     ListNode(int x) : val(x), next(nullptr) {}\n *     ListNode(int x, ListNode *next) : val(x), next(next) {}\n * };\n */\n\nclass Solution {\npublic:\n    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {\n        ListNode *point1 = list1;\n        int count = 1;\n        while (count != a)\n        {\n            point1 = point1 -> next;\n            count++;\n        }\n\n        ListNode *point2 = point1 -> next;\n        while (count != b+1)\n        {\n            point2 = point2 -> next;\n            count++;\n        }\n\n        point1->next = list2;\n        ListNode *temp = list2;\n        while (temp -> next != NULL)\n            temp = temp -> next;\n\n        temp -> next = point2;\n        \n        return list1;\n\n    }\n};\n```
['C++']