Question

(15 pts) Describe an O(n)-time algorithm that partitions a doubly linked list L into two doubly linked lists L1 and L2, where L1 contains the odd-number-th elements in L and L2 contains the even-number-th elements in L. Elements in both L1 and L2 should appear in the same order as they appear in L. For example, if L contains the numbers 4, 7, 9, 1, and -3, in that order, then the output L1 should contain 4, 9, and -3, in that order, and L2 should contain 7 and 1, in that order.

Answer 1

1. First of all we take two head i.e head1 is the head of L1 i.e odd number -th node and head 2 is the head of L2 i.e head of the even number-th node. also we have a counter variable called count=1 which is used to decide that current node odd number-th or even number by calculating count%2==0 means even number otherwise odd number.
2. Declare three temporary node temp1=head1,temp2=head2,current=head i.e head of list L
3. while current !=null do:
   • if count %2==0 : i.e even th number node then
     • if(head2==null) // beacause initially head1 and head2 is null
       • head2=current;
       • temp2=current;
       • head2.prev=null;
     • else
       • temp2.next=current
       • current.prev=temp2;
       • temp2=current;
   • else i.e odd th number node
     • if(head1==null)
       • head1=current;
       • temp1=current;
       • head1.prev=null;
     • ​​​​​​​else
       • temp1.next=current
       • current.prev=temp1;
       • temp1=current;
   • count=count+1;
   • current=current.next;
4. temp1.next=null;
5. temp2.next=null;
6. return head1 and head 2.