CodeStepByStep

Write a function named surround that accepts three parameters: a reference to a pointer to the front of a linked list of integers; an integer value A, and an integer value B. Your function should locate any nodes storing the value A and place new nodes directly before and after them storing the value B. Suppose, for example, that a variable named front points to the front of a list storing the following values:

front -> 1 -> 2 -> 3 -> 4 -> 2 -> 5 /

If we make the call of surround(front, 2, 9); the list's state should become:

front -> 1 -> 9 -> 2 -> 9 -> 3 -> 4 -> 9 -> 2 -> 9 -> 5 /

              |         |              |         |
               \_______/                \_______/
              surrounded               surrounded

Notice that a value of 9 has been inserted before and after every occurrence of the value 2. If the list had instead stored:

front -> 7 -> 0 -> 1 -> 3 -> 7 -> 7 -> 4 -> 7 /

Then a call of surround(front, 7, 0); would surround all 7s with 0s, changing the list to store the following:

front -> 0 -> 7 -> 0 -> 0 -> 1 -> 3 -> 0 -> 7 -> 0 -> 0 -> 7 -> 0 -> 4 -> 0 -> 7 -> 0 /

Your function should work properly even if the values A and B are the same. For example, if the list contains:

front -> 3 -> 3 -> 3 /

Then a call of surround(front, 3, 3); would surround all 3s with 3s, changing the list to store the following:

front -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 -> 3 /

If the list contains no occurrences of the value A, it should not be modified by your function. Your function should work properly for a list of any size.

Note: The goal of this problem is to modify the list by modifying pointers. It might be easier to solve it in other ways, such as by changing nodes' data values or by rebuilding an entirely new list, but such tactics are forbidden.

Constraints:

• Your code should run in no worse than O(N) time, where N is the length of the list. Your code must make a single pass over the list (not multiple passes).
• Note that the list has no "size" function, nor are you allowed to loop over the whole list to count its size.
• Do not use any auxiliary data structures such as arrays, vectors, queues, strings, maps, sets, etc.
• Do not modify the data field of any nodes; you must solve the problem by changing the links between nodes.
• You may create new ListNode objects, and you may create as many ListNode* pointers as you like. But do not construct any more new ListNode objects than needed.

Assume that you are using the ListNode structure as defined below:

struct ListNode {
    int data;         // value stored in each node
    ListNode* next;   // pointer to next node in list (nullptr if none)
};