Difference between revisions of "TADM2E 3.2"

From Algorithm Wiki
Jump to: navigation, search
(Recovering wiki)
m (Matt moved page Algorithm Wiki:TADM2E 3.2 to TADM2E 3.2 over redirect: revert)
 
(9 intermediate revisions by 6 users not shown)
Line 1: Line 1:
 +
'''C'''
 
<pre>
 
<pre>
 
typedef struct Node {
 
typedef struct Node {
Line 28: Line 29:
 
}
 
}
 
</pre>
 
</pre>
 +
----
 +
'''Dart'''
 +
<pre>
 +
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
 +
}
 +
</pre>
 +
----
 +
 +
'''In Java
 +
'''
 +
<pre>
 +
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);
 +
    }
 +
 +
}
 +
</pre>
 +
 +
----
 +
'''In Python
 +
'''
 +
<pre>
 +
 +
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
 +
</pre>
 +
  
 +
----
  
 
[[Data-structures-TADM2E|Back to ''Data Structures'' Problems]]...
 
[[Data-structures-TADM2E|Back to ''Data Structures'' Problems]]...

Latest revision as of 12:03, 2 August 2020

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...