Java

Create a Linked List data structure by writing your own Linked List class which contains a node class.Just the way we explored it in the Lecture, your node class will house the data (integer in this case) and a pointer to the next node element. Populate your linked list with the following integers and print it (you need to also print the commas).

50, 11, 33, 21, 40, 71

Delete Nth node from the end of the linked list and print the linked list after deletion. Here N = 2 Below is the expected output after deleting the second last element. 50, 11, 33, 21, 71

Note, here we do not know the length of the list. Complete the above deletion operation without calculating the length of the list. Your solution should only make a single pass through the linked list, adhering to O(n) time complexity overall and O(1) space complexity.

Hint: Maintain two pointers: a Fast Pointer and a Slow pointer. Initialize both pointers to a dummy node which points to the head of the list. Then starting a counter from zero, move the fast pointer two places forward, to maintain a gap of two between the fast and slow pointers and then move both in tandem. Finally, when the fast pointer reaches the end of the list, the slow pointer will be at the third last node. You can now delete the second last node.

Please include comments and test cases!