4. (15 pts) Give the pseudocode of an O(n)-time algorithm that splits a doubly linked list / 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 Ind, 4th ..., nodes of L. Recall that a doubly linked list has both head and tail pointers. Justify the running time of your algorithm. 4. (15 pts) Give the pseudocode of an O(n)-time algorithm that splits a doubly linked list / 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 Ind, 4th ..., nodes of L. Recall that a doubly linked list has both head and tail pointers. Justify the running time of your algorithm