Merge Linked Lists In Between Indices
Intuition\nWe need to merge list2 into list1 by removing a portion of list1 specified by indices a and b.\n\n# Approach\nTraverse list1 until reaching the node 
# Intuition\nWe need to merge list2 into list1 by removing a portion of list1 specified by indices a and b.\n\n# Approach\n*Traverse list1 until reaching the node just before index a and store this node in prev.\n\n*Keep track of the node at index a in track.\n\n*Traverse list1 until reaching the node at index b.\n\n*Point track to the head of list2,then traverse list2.\n\n*Connect end of list2 to list1.\n\n*Return the merged list.\n\n# Complexity\n- Time complexity:\n\nThe time complexity of the provided solution is O(n), where n is the number of nodes in list1. \n\n> This is because we iterate through[]() list1 twice:\n*Once to find the nodes at indices a-1 and b.\n*Once to find the end of list2. All other operations   are constant time.\n\n- Space complexity:\nThe space complexity is O(1) because we are not using any extra space.\n\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 */\nclass Solution {\npublic:\n    ListNode* mergeInBetween(ListNode* list1, int a, int b, ListNode* list2) {\n        ListNode* prev=list1;\n\n        //prev will point in node one before a\n        for(int i=0;i<a-1;i++)\n        {\n            prev=prev->next;\n        }\n\n        ListNode* track=prev;\n\n        for(int i=a;i<=b;i++)\n        {\n            prev=prev->next;\n        }\n\n        //traversing list2\n        track->next=list2;\n        ListNode* end=list2;\n        while(end->next!=NULL)\n        {\n            end=end->next;\n        }\n\n        //connnect end to prev of list1\n        end->next=prev->next;\n\n        return list1;\n    }\n};\n```
['C++']