Difference between revisions of "TADM2E 3.2"

Revision as of 18:49, 27 November 2018

C

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;
}

Dart

class Node<T> {
  Node(this.value, [this.next]);
  T value;
  Node next;
  @override String toString() => '$value $next';
}

Node reverse(Node n) {
  Node curr = n.next;
  n.next = null;		// `n` is the new tail.
  while(curr != null) {
    Node tmp = curr.next;	// Start swap.
    curr.next = n;		// next => previous
    n = curr;			// Update loop's previous node.
    curr = tmp;			// Update loop's current node.
  }
  return n;
}

// Example
void main() {
  final list = Node(1, Node(2, Node(3, Node(4, Node(5)))));
  print(list);			// 1 2 3 4 5 null
  print(reverse(list));		// 5 4 3 2 1 null
}

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);
    }

}

In Python

class Node():
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList():
    def __init__(self):
        self.head = None
        self.tail = None

    def add_node(self, value):
        if not self.head:
            self.__initialize_list(value)
        else:
            node = Node(value)
            self.tail.next = node
            self.tail = node

    def print_list(self):
        current_node = self.head

        print('head ->'),
        while current_node is not None:
            print(current_node.value),

            current_node = current_node.next

            print('->'),

        print('tail')

    def reverse(self):
        current_head = self.head
        head = self.head

        while current_head is not None:
            temp = current_head
            current_head = head.next
            t_next = current_head.next
            head.next = t_next
            current_head.next = temp

            if head.next is None:
                self.head = current_head
                break

    def __initialize_list(self, value):
        self.head = Node(value)
        self.tail = self.head

Back to Data Structures Problems...