Difference between revisions of "TADM2E 3.2"

Revision as of 19:27, 10 April 2015

typedef struct Node {
    char *value;
    struct Node *next;
} Node;

int reverse(Node **head) {
    Node *curr, *prev, *next;

    if (!head || !(*head)) {
        return 0;
    }

    curr = *head;
    prev = NULL;
    next = NULL;

    while (curr) {
        next =  curr->next;
        curr->next = prev;
        prev = curr;
        curr = next;
    }

    *head = prev;

    return 1;
}

============================================

[[In Java ]] class ListNode {

   int val;
   ListNode next;

   ListNode(final int x) {
       val = x;
       next = null;
   }

}

public class LinkedList {

   ListNode head;

   public LinkedList() {
       head = null;
   }

   public void prepend(final int in) {
       final ListNode data = new ListNode(in);
       data.next = head;
       head = data;
   }

   public void appendToList(final int in) {
       final ListNode data = new ListNode(in);
       ListNode current = head;
       if (head == null) {
           head = data;
           return;
       }
       while (current.next != null) {
           current = current.next;
       }
       current.next = data;
   }

   public void printList(final ListNode head) {
       ListNode current = head;
       while (current != null) {
           System.out.print(current.val + " -> ");
           current = current.next;
       }
       System.out.println();
   }
   
   public ListNode reverseList(final ListNode node) {
       //what if 0 node in list
       if (node == null) {
           return null;
       }
       //what if 1 node in list
       if (node.next == null) {
           return node;
       }
       //what if multiple nodes.divide into two parts . reverse second part recursively and in end point second.next to first 
       final ListNode secondElem = node.next;
       node.next = null;
       final ListNode reverseRest = reverseList(secondElem);
       secondElem.next = node;
       return reverseRest;
   }
   
   public static void main(final String[] args) {
       final LinkedList linkedList = new LinkedList();
       linkedList.appendToList(12);
       linkedList.appendToList(13);
       linkedList.appendToList(14);
       linkedList.appendToList(15);
       linkedList.printList(linkedList.head);
       final ListNode head = linkedList.reverseList(linkedList.head);
       linkedList.printList(head);
   }

}

Back to Data Structures Problems...