CareerCup

They have just asked us to write a code to test the reverse function written to reverse a linked list.

Assume

Node * reverse(Node * head)

returns a pointer to the linked list which is reversed.

So something like, should work.

Node * reverseReverse = reverse(reverse(orig));
	boolean compare(Node * orig, Node * reverseReverse)
	{
		Node * temp = orig; Node * temp1 = reverseReverse
		if(temp == NULL & temp1 == NULL)
			return true;
		while(temp != NULL && temp1 != NULL)
		{
			if(temp->value != temp1->value)
				return false;
		}
		if((temp != NULL && temp1 == NULL) || (temp == NULL && temp != NULL))
			return false;
		return true;
	}

typedef struct LinkList
     {
                  int info;
                  struct LinkList *next;
     } node;
     
     node *start;

     void ReverseList(node** start)
     {
                node *prev, *curr, *nnext;
                prev = (node*) NULL;
                curr = *start;
                nnext = curr->next;
                curr->next = (node*) NULL;
                while(nnext != (node*)NULL)
                {
                                prev = curr;
                                curr = nnext;
                                nnext = curr->next;
                                curr->next = prev;
                 }
                 *start = curr;
      }

How about this:

Node* reverseLinkList(Node **head)
{
	Node *pre=null;
	Node *next=null;
	while(*head!=null)
	{
		next=*head->next;
		*head->next=pre;
		pre=*head;
		*head=next;
	}

	return *head;
}

ListNode *reverse(ListNode *head)
        {
              if(head == NULL || head->next == NULL)
			return head;

	      ListNode *temp = head->next;
	      ListNode *retP =  reverse(temp);
	      temp->next = head;
	      head->next = NULL;
	      return retP;
        }

This maybe not the most elegant of the code. However, it works:

public static void reversell(LinkList ll)
	{

		LinkListNode curr = ll.getHead();
		LinkListNode temp1;
		LinkListNode temp2 = null;
		
		/*
		 * Remember this loop runs for every alternate node.
		 * i.e. for 1,2,3,4,5. curr will have 1,3,5
		 * However, the in between are taken care in the body loop.
		 */
		while (curr.getLink() != null && curr.getLink().getLink() != null)
		{
			// We would need this as we update curr to next node
			temp1 = curr;
			
			/* Storing the next and the next to next node
			 * as we loose track of next we do loose track 
			 * of next to next as well
			 */
			LinkListNode nextNode = curr.getLink();
			LinkListNode nextNextNode = curr.getLink().getLink();
			
			// temp 2 for root will be null. However, we update it with the nextNode later on.
			curr.setLink(temp2);
			curr=nextNode;
			
			//Last node update. So that in next iteration you know your last node.
			temp2= curr;
			
			//Updating nextNode with earlier node.
			curr.setLink(temp1);
			
			//Update on curr
			curr=nextNextNode; 	
		}
		// Case when you have odd number of elements and you loop out on last 
		// element because curr.getLink() gets 0.
		if (curr.getLink() == null)
			curr.setLink(temp2);
		else
		{
			// Case when you have even number of elements and you loop out on last 
			// element because curr.getLink().getLink() gets 0.
			temp1=curr.getLink();
			curr.setLink(temp2);
			temp1.setLink(curr);
		}
	}

How about this?

public static void revll(Nodes p)
    {
        Nodes temp=p;
        Nodes temp2=p;
      if(temp2==null)
      {     System.out.println("Invalid"); System.exit(0);}
        
        int count=1;
        while(p.next!=null)
        {
            p=p.next;
            count++;
        }
        int a[]=new int[count-1];
        Nodes checkend=new Nodes();
        if(p!=null)
        {
           System.out.print(p.value+"\t");
           checkend=p;
        }
        int i=0;
        while(temp!=checkend)
        {
           a[i]=temp.value;
           i++;
           temp=temp.next;
        }
       //Printing the rest of the elements
        for(int j=a.length-1;j>=0;j--)
        {
            System.out.print(a[j]+"\t");
        }
    }

public void checkReverseLinkedListProg() {
		// TODO Auto-generated method stub

		LinkedList L1 = new LinkedList();
		LinkedList L2 = new LinkedList();

		L1.add("a");
		L1.add("b");
		L1.add("c");
		L1.add("d");

		L2.add("d");
		L2.add("c");
		L2.add("b");
		L2.add("a");

		ListIterator<String> it1 = L1.listIterator();

		Iterator<String> it2 = L2.descendingIterator();

		String a = null;
		String b = null;
		String flag = "true";
		while(it1.hasNext()){
			if((a=it1.next()) != (b=it2.next())){
				flag = "false";
				System.out.println("function to reverse a linked list is NOT CORRECT");
				break;
			}
		}
		if (flag == "true"){
			System.out.println("function to reverse a linked list is CORRECT");
		}
	}

Assume we're to test following reverse function

node *reverse(node *head)

To test this, write another function with following header

int test_reverse(node *head)

In test_reverse, create a copy of input list, and call reverse on list twice

node *copied = clone( head ) /* returns a duplicate copy of same linked list */
reverse( reverse( copied ) ); /* called it twice, should match with original list */
return compare (head, copied ) / * compare two lists, if they're same in content then its fine */

If content matching is not allowed then we'll have to store value of each pointer in another auxillary list and compare those with reverse(reverse(copied))