Hello I need help with a computer science problem Dealing wi

Hello, I need help with a computer science problem. Dealing with a circular linked list with a set of numbers, I need to swap a large set of numbers within the list. For example, given the numbers 1 2 3 4 5 6 7 8 9, I need to swap the numbers BEFORE 4 for the numbers AFTER 5. Giving: 4 5 1 2 3 6 7 8 9

Please don\'t give me the answer, but please explain how I would go about accomplishing this task. Thank you.

PS. I would think you maybe make an array to store the numbers, then put the numbers from the array into the circular linked list at the proper spot. I don\'t know if i am allowed to do this, but any help would be appreciated, thank you!

Solution

If you are good with circular linked list functions implementation like insertNodeAtPosition(), deleteNodeFromPosition(), searchNodeWithValue() etc, now you can do this using the following methodology.

1. Find the node position for the before value, and store it in a variable say tillPos.

2. Now find the node position for the after value, and store it in the variable say fromPos.

3. Initialize a traverseIndex variable to 1.

Now run a loop, Starting from head(first element in the list), till the tillPos position, everytime, call the function deleteNodeFromPosition(), with traverseIndex as position value, and store the returned value/node pointer in a variable.

In the same loop as the next step, call the insertNodeAtPosition() with fromPos as an input parameter.

(Note that you don\'t have to increment the traverseIndex, and fromPos, as they will be the same for all the variables.)

So, for the example you specified, the lists after each loop will look like this:

And thats how you could do this, if you are not allowed to used an extra space.

If you\'re comfortable with the logic you specified like using arrays to store, and re-enter into the list, you can also do that way, provided you\'re allowed to use an extra space. The reason is, in realtime, taking an extra space is not a better idea to go with.