(15 pts) Give the pseudocode of an O(n)-time algorithm that splits a doubly linked list L into two doubly linked lists, where one of the resulting lists contains odd number-th nodes of L and the other contains even-number-th nodes of L. More precisely, the algorithm on input L should return two doubly linked lists Li and L2, where Li contains the 1st, 3rd, ..., nodes of L and L2 contains the 2nd, 4th, ..., nodes of L. Recall that a doubly linked list has both head and tail pointers. Justify the running time of your algorithm