|
|
| Line 1: |
Line 1: |
| − | '''C'''
| + | 1. size 4 array with 3 elements. remove 1, insert 1, and so forth. <br> |
| − | <pre> | + | 2. when the array is one-fourth full, shrink its size to half of what it was. |
| − | typedef struct Node {
| |
| − | char *value;
| |
| − | struct Node *next;
| |
| − | } Node;
| |
| | | | |
| − | int reverse(Node **head) {
| |
| − | Node *curr, *prev, *next;
| |
| | | | |
| − | if (!head || !(*head)) {
| + | Back to [[Chaprer 3]] |
| − | return 0;
| |
| − | }
| |
| − | | |
| − | curr = *head;
| |
| − | prev = NULL;
| |
| − | next = NULL;
| |
| − | | |
| − | while (curr) {
| |
| − | next = curr->next;
| |
| − | curr->next = prev;
| |
| − | prev = curr;
| |
| − | curr = next;
| |
| − | }
| |
| − | | |
| − | *head = prev;
| |
| − | | |
| − | return 1;
| |
| − | }
| |
| − | </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>
| |
| − | | |
| − | | |
| − | ----
| |
| − | | |
| − | Back to [[Chapter 3]] | |
