COMP2011 Tutorial Solutions 5, Week 6

Linked Lists

1. C-4.11: Describe in pseudo-code a linear-time algorithm for reversing a singly linked list L, so that the ordering of the nodes becomes exactly opposite of what it was before.

   ListNode Reverse( ListNode L )
   {
       ListNode curr = L;
       ListNode tail = null;
       ListNode prev = null;
   
       while( curr != null ) {
           prev = curr;
           curr = prev.getNext();
           prev.setNext( tail );
           tail = prev;
       }
       return( tail );
   }
   

2. C-4.12: Give an algorithm for concatenating two singly linked lists L and M, with header sentinel nodes, into a single list L' that contains all the nodes of L (in their original order) followed by all the nodes of M (in their original order). What is the running time of this method, if we let n denote the number of nodes in L and we let m denote the number of nodes in M?

       node = L.header;
   
       while( node.getNext() != null ) {
           node = node.getNext();
       }
       node.setNext( M.header.getNext());
   
       L.size = L.size + M.size;
   
       return L;
   

   Running time is O(n).

3. C-4.13: Give an algorithm for concatenating two doubly linked lists L and M, with header and trailer sentinel nodes, into a new list L', as in the previous exercise. What is the running time of this method?

      ( L.trailer.getPrev()).setNext( M.header.getNext());
      ( M.header.getNext()).setPrev( L.trailer.getPrev());
   
       L.trailer = M.trailer;
       L.size = L.size + M.size;
   
       return L;
   

   Running time is O(1).

4. C-4.15: Describe in pseudo-code how to swap two nodes x and y in a singly linked list L given references only to x and y. Repeat this exercise for the case when L is a doubly linked list. What are the running times of each of these methods in terms of n, the number of nodes in L?

   Singly linked list (note: we assume header sentinel node):

   ListNode xprev = L.header;
   ListNode yprev = L.header;
   
   if( x == y ) {
       return;
   }
   while(( x_prev != null )&&( x_prev.getNext() != x )) {
       x_prev = x_prev.getNext();
   }
   while(( y_prev != null )&&( y_prev.getNext() != y )) {
       y_prev = y_prev.getNext();
   }
   if(( x_prev == null )||( y_prev == null )) {
       throw new NodeNotFoundException();
   }
   if( y_prev == x ) {
   
       x.setNext( y.getNext());
       y.setNext( x );
       x_prev.setNext( y );
   }
   else if( x_prev == y ) {
   
       y.setNext( x.getNext());
       x.setNext( y );
       y_prev.setNext( x );
   }
   else {
       Node tmp = x.getNext();
       x.setNext( y.getNext());
       y.setNext( tmp );
   
       x_prev.setNext( y );
       y_prev.setNext( x );
   }
   

   Running time is O(n).

   Doubly linked list (note: we assume header and trailer sentinel nodes):

   Node x_prev = x.getPrev();
   Node y_prev = y.getPrev();
   
   if( x == y ) {
       return;
   }
   if( y_prev == x ) {
   
       x.setNext( y.getNext());
       y.setNext( x );
       x_prev.setNext( y );
       y.setPrev( x_prev );
   }
   else if( x_prev == y ) {
   
       y.setNext( x.getNext());
       x.setNext( y );
       y_prev.setNext( x );
       x.setPrev( y_prev );
   }
   else {
       Node tmp = x.getNext();
       x.setNext( y.getNext());
       y.setNext( tmp );
   
       x_prev.setNext( y );
       y.setPrev( x_prev );
   
       y_prev.setNext( x );
       x.setPrev( y_prev );
   }
   x.getNext().setPrev( x );
   y.getNext().setPrev( y );
   

   Running time is O(1).

Author: Alan Blair