Dadas dos listas enlazadas que representan dos números positivos grandes. Resta el número más pequeño del más grande y devuelve la diferencia como una lista enlazada. Tenga en cuenta que las listas de entrada pueden estar en cualquier orden, pero siempre debemos restar las más pequeñas de las más grandes.
Se puede suponer que no hay ceros iniciales adicionales en las listas de entrada.
Ejemplos:
Input: l1 = 1 -> 0 -> 0 -> NULL, l2 = 1 -> NULL Output: 0->9->9->NULL Explanation: Number represented as lists are 100 and 1, so 100 - 1 is 099 Input: l1 = 7-> 8 -> 6 -> NULL, l2 = 7 -> 8 -> 9 NULL Output: 3->NULL Explanation: Number represented as lists are 786 and 789, so 789 - 786 is 3, as the smaller value is subtracted from the larger one.
Enfoque : Los siguientes son los pasos.
- Calcular tamaños de dos listas enlazadas dadas.
- Si los tamaños no son iguales, agregue ceros en la lista enlazada más pequeña.
- Si el tamaño es el mismo, siga los pasos a continuación:
- Encuentre la lista enlazada de menor valor.
- Uno por uno, reste los Nodes de la lista enlazada de tamaño más pequeño del tamaño más grande. Lleve un registro de los préstamos mientras resta.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to subtract smaller valued list from
// larger valued list and return result as a list.
#include <bits/stdc++.h>
using namespace std;
// A linked List Node
struct Node {
int data;
struct Node* next;
};
// A utility which creates Node.
Node* newNode(int data)
{
Node* temp = new Node;
temp->data = data;
temp->next = NULL;
return temp;
}
/* A utility function to get length
of linked list */
int getLength(Node* Node)
{
int size = 0;
while (Node != NULL) {
Node = Node->next;
size++;
}
return size;
}
/* A Utility that padds zeros in front of the
Node, with the given diff */
Node* paddZeros(Node* sNode, int diff)
{
if (sNode == NULL)
return NULL;
Node* zHead = newNode(0);
diff--;
Node* temp = zHead;
while (diff--) {
temp->next = newNode(0);
temp = temp->next;
}
temp->next = sNode;
return zHead;
}
/* Subtract LinkedList Helper is a recursive function,
move till the last Node, and subtract the digits and
create the Node and return the Node. If d1 < d2, we
borrow the number from previous digit. */
Node* subtractLinkedListHelper(Node* l1, Node* l2,
bool& borrow)
{
if (l1 == NULL && l2 == NULL && borrow == 0)
return NULL;
Node* previous = subtractLinkedListHelper(
l1 ? l1->next : NULL, l2 ? l2->next : NULL, borrow);
int d1 = l1->data;
int d2 = l2->data;
int sub = 0;
/* if you have given the value to next digit then
reduce the d1 by 1 */
if (borrow) {
d1--;
borrow = false;
}
/* If d1 < d2, then borrow the number from previous
digit. Add 10 to d1 and set borrow = true; */
if (d1 < d2) {
borrow = true;
d1 = d1 + 10;
}
/* subtract the digits */
sub = d1 - d2;
/* Create a Node with sub value */
Node* current = newNode(sub);
/* Set the Next pointer as Previous */
current->next = previous;
return current;
}
/* This API subtracts two linked lists and returns the
linked list which shall have the subtracted result. */
Node* subtractLinkedList(Node* l1, Node* l2)
{
// Base Case.
if (l1 == NULL && l2 == NULL)
return NULL;
// In either of the case, get the lengths of both
// Linked list.
int len1 = getLength(l1);
int len2 = getLength(l2);
Node *lNode = NULL, *sNode = NULL;
Node* temp1 = l1;
Node* temp2 = l2;
// If lengths differ, calculate the smaller Node
// and padd zeros for smaller Node and ensure both
// larger Node and smaller Node has equal length.
if (len1 != len2) {
lNode = len1 > len2 ? l1 : l2;
sNode = len1 > len2 ? l2 : l1;
sNode = paddZeros(sNode, abs(len1 - len2));
}
else {
// If both list lengths are equal, then calculate
// the larger and smaller list. If 5-6-7 & 5-6-8
// are linked list, then walk through linked list
// at last Node as 7 < 8, larger Node is 5-6-8
// and smaller Node is 5-6-7.
while (l1 && l2) {
if (l1->data != l2->data) {
lNode = l1->data > l2->data ? temp1 : temp2;
sNode = l1->data > l2->data ? temp2 : temp1;
break;
}
l1 = l1->next;
l2 = l2->next;
}
}
// If both lNode and sNode still have NULL value,
// then this means that the value of both of the given
// linked lists is the same and hence we can directly
// return a node with value 0.
if (lNode == NULL && sNode == NULL) {
return newNode(0);
}
// After calculating larger and smaller Node, call
// subtractLinkedListHelper which returns the subtracted
// linked list.
bool borrow = false;
return subtractLinkedListHelper(lNode, sNode, borrow);
}
/* A utility function to print linked list */
void printList(struct Node* Node)
{
while (Node != NULL) {
printf("%d ", Node->data);
Node = Node->next;
}
printf("\n");
}
// Driver program to test above functions
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(0);
head1->next->next = newNode(0);
Node* head2 = newNode(1);
Node* result = subtractLinkedList(head1, head2);
printList(result);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
C
// C program to subtract smaller valued list from
// larger valued list and return result as a list.
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
// A linked List Node
typedef struct Node {
int data;
struct Node* next;
} Node;
// A utility which creates Node.
Node* newNode(int data)
{
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = data;
temp->next = NULL;
return temp;
}
/* A utility function to get length
of linked list */
int getLength(Node* Node)
{
int size = 0;
while (Node != NULL) {
Node = Node->next;
size++;
}
return size;
}
/* A Utility that padds zeros in front of the
Node, with the given diff */
Node* paddZeros(Node* sNode, int diff)
{
if (sNode == NULL)
return NULL;
Node* zHead = newNode(0);
diff--;
Node* temp = zHead;
while (diff--) {
temp->next = newNode(0);
temp = temp->next;
}
temp->next = sNode;
return zHead;
}
/* Subtract LinkedList Helper is a recursive function,
move till the last Node, and subtract the digits and
create the Node and return the Node. If d1 < d2, we
borrow the number from previous digit. */
static bool borrow;
Node* subtractLinkedListHelper(Node* l1, Node* l2)
{
if (l1 == NULL && l2 == NULL && borrow == 0)
return NULL;
Node* previous = subtractLinkedListHelper(
l1 ? l1->next : NULL, l2 ? l2->next : NULL);
int d1 = l1->data;
int d2 = l2->data;
int sub = 0;
/* if you have given the value to next digit then
reduce the d1 by 1 */
if (borrow) {
d1--;
borrow = false;
}
/* If d1 < d2, then borrow the number from previous
digit. Add 10 to d1 and set borrow = true; */
if (d1 < d2) {
borrow = true;
d1 = d1 + 10;
}
/* subtract the digits */
sub = d1 - d2;
/* Create a Node with sub value */
Node* current = newNode(sub);
/* Set the Next pointer as Previous */
current->next = previous;
return current;
}
/* This API subtracts two linked lists and returns the
linked list which shall have the subtracted result. */
Node* subtractLinkedList(Node* l1, Node* l2)
{
// Base Case.
if (l1 == NULL && l2 == NULL)
return NULL;
// In either of the case, get the lengths of both
// Linked list.
int len1 = getLength(l1);
int len2 = getLength(l2);
Node *lNode = NULL, *sNode = NULL;
Node* temp1 = l1;
Node* temp2 = l2;
// If lengths differ, calculate the smaller Node
// and padd zeros for smaller Node and ensure both
// larger Node and smaller Node has equal length.
if (len1 != len2) {
lNode = len1 > len2 ? l1 : l2;
sNode = len1 > len2 ? l2 : l1;
sNode = paddZeros(sNode, abs(len1 - len2));
}
else {
// If both list lengths are equal, then calculate
// the larger and smaller list. If 5-6-7 & 5-6-8
// are linked list, then walk through linked list
// at last Node as 7 < 8, larger Node is 5-6-8
// and smaller Node is 5-6-7.
while (l1 && l2) {
if (l1->data != l2->data) {
lNode = l1->data > l2->data ? temp1 : temp2;
sNode = l1->data > l2->data ? temp2 : temp1;
break;
}
l1 = l1->next;
l2 = l2->next;
}
}
// If both lNode and sNode still have NULL value,
// then this means that the value of both of the given
// linked lists is the same and hence we can directly
// return a node with value 0.
if (lNode == NULL && sNode == NULL) {
return newNode(0);
}
// After calculating larger and smaller Node, call
// subtractLinkedListHelper which returns the subtracted
// linked list.
borrow = false;
return subtractLinkedListHelper(lNode, sNode);
}
/* A utility function to print linked list */
void printList(struct Node* Node)
{
while (Node != NULL) {
printf("%d ", Node->data);
Node = Node->next;
}
printf("\n");
}
// Driver program to test above functions
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(0);
head1->next->next = newNode(0);
Node* head2 = newNode(1);
Node* result = subtractLinkedList(head1, head2);
printList(result);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
Java
// Java program to subtract smaller valued
// list from larger valued list and return
// result as a list.
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList {
static Node head; // head of list
boolean borrow;
/* Node Class */
static class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d)
{
data = d;
next = null;
}
}
/* A utility function to get length of
linked list */
int getLength(Node node)
{
int size = 0;
while (node != null) {
node = node.next;
size++;
}
return size;
}
/* A Utility that padds zeros in front
of the Node, with the given diff */
Node paddZeros(Node sNode, int diff)
{
if (sNode == null)
return null;
Node zHead = new Node(0);
diff--;
Node temp = zHead;
while ((diff--) != 0) {
temp.next = new Node(0);
temp = temp.next;
}
temp.next = sNode;
return zHead;
}
/* Subtract LinkedList Helper is a recursive
function, move till the last Node, and
subtract the digits and create the Node and
return the Node. If d1 < d2, we borrow the
number from previous digit. */
Node subtractLinkedListHelper(Node l1, Node l2)
{
if (l1 == null && l2 == null && borrow == false)
return null;
Node previous
= subtractLinkedListHelper(
(l1 != null) ? l1.next
: null,
(l2 != null) ? l2.next : null);
int d1 = l1.data;
int d2 = l2.data;
int sub = 0;
/* if you have given the value to
next digit then reduce the d1 by 1 */
if (borrow) {
d1--;
borrow = false;
}
/* If d1 < d2, then borrow the number from
previous digit. Add 10 to d1 and set
borrow = true; */
if (d1 < d2) {
borrow = true;
d1 = d1 + 10;
}
/* subtract the digits */
sub = d1 - d2;
/* Create a Node with sub value */
Node current = new Node(sub);
/* Set the Next pointer as Previous */
current.next = previous;
return current;
}
/* This API subtracts two linked lists and
returns the linked list which shall have the
subtracted result. */
Node subtractLinkedList(Node l1, Node l2)
{
// Base Case.
if (l1 == null && l2 == null)
return null;
// In either of the case, get the lengths
// of both Linked list.
int len1 = getLength(l1);
int len2 = getLength(l2);
Node lNode = null, sNode = null;
Node temp1 = l1;
Node temp2 = l2;
// If lengths differ, calculate the smaller
// Node and padd zeros for smaller Node and
// ensure both larger Node and smaller Node
// has equal length.
if (len1 != len2) {
lNode = len1 > len2 ? l1 : l2;
sNode = len1 > len2 ? l2 : l1;
sNode = paddZeros(sNode, Math.abs(len1 - len2));
}
else {
// If both list lengths are equal, then
// calculate the larger and smaller list.
// If 5-6-7 & 5-6-8 are linked list, then
// walk through linked list at last Node
// as 7 < 8, larger Node is 5-6-8 and
// smaller Node is 5-6-7.
while (l1 != null && l2 != null) {
if (l1.data != l2.data) {
lNode = l1.data > l2.data ? temp1 : temp2;
sNode = l1.data > l2.data ? temp2 : temp1;
break;
}
l1 = l1.next;
l2 = l2.next;
}
}
// After calculating larger and smaller Node,
// call subtractLinkedListHelper which returns
// the subtracted linked list.
borrow = false;
return subtractLinkedListHelper(lNode, sNode);
}
// function to display the linked list
static void printList(Node head)
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
}
// Driver program to test above
public static void main(String[] args)
{
Node head = new Node(1);
head.next = new Node(0);
head.next.next = new Node(0);
Node head2 = new Node(1);
LinkedList ob = new LinkedList();
Node result = ob.subtractLinkedList(head, head2);
printList(result);
}
}
// This article is contributed by Chhavi
Python
# Python program to subtract smaller valued list from
# larger valued list and return result as a list.
# A linked List Node
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
# A utility which creates Node.
def newNode(data):
temp = Node(0)
temp.data = data
temp.next = None
return temp
# A utility function to get length of linked list
def getLength(Node):
size = 0
while (Node != None):
Node = Node.next
size = size + 1
return size
# A Utility that padds zeros in front of the
# Node, with the given diff
def paddZeros( sNode, diff):
if (sNode == None):
return None
zHead = newNode(0)
diff = diff - 1
temp = zHead
while (diff > 0):
diff = diff - 1
temp.next = newNode(0)
temp = temp.next
temp.next = sNode
return zHead
borrow = True
# Subtract LinkedList Helper is a recursive function,
# move till the last Node, and subtract the digits and
# create the Node and return the Node. If d1 < d2, we
# borrow the number from previous digit.
def subtractLinkedListHelper(l1, l2):
global borrow
if (l1 == None and l2 == None and not borrow ):
return None
l3 = None
l4 = None
if(l1 != None):
l3 = l1.next
if(l2 != None):
l4 = l2.next
previous = subtractLinkedListHelper(l3, l4)
d1 = l1.data
d2 = l2.data
sub = 0
# if you have given the value to next digit then
# reduce the d1 by 1
if (borrow):
d1 = d1 - 1
borrow = False
# If d1 < d2, then borrow the number from previous digit.
# Add 10 to d1 and set borrow = True
if (d1 < d2):
borrow = True
d1 = d1 + 10
# subtract the digits
sub = d1 - d2
# Create a Node with sub value
current = newNode(sub)
# Set the Next pointer as Previous
current.next = previous
return current
# This API subtracts two linked lists and returns the
# linked list which shall have the subtracted result.
def subtractLinkedList(l1, l2):
# Base Case.
if (l1 == None and l2 == None):
return None
# In either of the case, get the lengths of both
# Linked list.
len1 = getLength(l1)
len2 = getLength(l2)
lNode = None
sNode = None
temp1 = l1
temp2 = l2
# If lengths differ, calculate the smaller Node
# and padd zeros for smaller Node and ensure both
# larger Node and smaller Node has equal length.
if (len1 != len2):
if(len1 > len2):
lNode = l1
else:
lNode = l2
if(len1 > len2):
sNode = l2
else:
sNode = l1
sNode = paddZeros(sNode, abs(len1 - len2))
else:
# If both list lengths are equal, then calculate
# the larger and smaller list. If 5-6-7 & 5-6-8
# are linked list, then walk through linked list
# at last Node as 7 < 8, larger Node is 5-6-8
# and smaller Node is 5-6-7.
while (l1 != None and l2 != None):
if (l1.data != l2.data):
if(l1.data > l2.data ):
lNode = temp1
else:
lNode = temp2
if(l1.data > l2.data ):
sNode = temp2
else:
sNode = temp1
break
l1 = l1.next
l2 = l2.next
global borrow
# After calculating larger and smaller Node, call
# subtractLinkedListHelper which returns the subtracted
# linked list.
borrow = False
return subtractLinkedListHelper(lNode, sNode)
# A utility function to print linked list
def printList(Node):
while (Node != None):
print (Node.data, end =" ")
Node = Node.next
print(" ")
# Driver program to test above functions
head1 = newNode(1)
head1.next = newNode(0)
head1.next.next = newNode(0)
head2 = newNode(1)
result = subtractLinkedList(head1, head2)
printList(result)
# This code is contributed by Arnab Kundu
C#
// C# program to subtract smaller valued
// list from larger valued list and return
// result as a list.
using System;
public class LinkedList {
static Node head; // head of list
bool borrow;
/* Node Class */
public class Node {
public int data;
public Node next;
// Constructor to create a new node
public Node(int d)
{
data = d;
next = null;
}
}
/* A utility function to get length of
linked list */
int getLength(Node node)
{
int size = 0;
while (node != null) {
node = node.next;
size++;
}
return size;
}
/* A Utility that padds zeros in front
of the Node, with the given diff */
Node paddZeros(Node sNode, int diff)
{
if (sNode == null)
return null;
Node zHead = new Node(0);
diff--;
Node temp = zHead;
while ((diff--) != 0) {
temp.next = new Node(0);
temp = temp.next;
}
temp.next = sNode;
return zHead;
}
/* Subtract LinkedList Helper is a recursive
function, move till the last Node, and
subtract the digits and create the Node and
return the Node. If d1 < d2, we borrow the
number from previous digit. */
Node subtractLinkedListHelper(Node l1, Node l2)
{
if (l1 == null && l2 == null && borrow == false)
return null;
Node previous = subtractLinkedListHelper((l1 != null) ? l1.next : null, (l2 != null) ? l2.next : null);
int d1 = l1.data;
int d2 = l2.data;
int sub = 0;
/* if you have given the value to
next digit then reduce the d1 by 1 */
if (borrow) {
d1--;
borrow = false;
}
/* If d1 < d2, then borrow the number from
previous digit. Add 10 to d1 and set
borrow = true; */
if (d1 < d2) {
borrow = true;
d1 = d1 + 10;
}
/* subtract the digits */
sub = d1 - d2;
/* Create a Node with sub value */
Node current = new Node(sub);
/* Set the Next pointer as Previous */
current.next = previous;
return current;
}
/* This API subtracts two linked lists and
returns the linked list which shall have the
subtracted result. */
Node subtractLinkedList(Node l1, Node l2)
{
// Base Case.
if (l1 == null && l2 == null)
return null;
// In either of the case, get the lengths
// of both Linked list.
int len1 = getLength(l1);
int len2 = getLength(l2);
Node lNode = null, sNode = null;
Node temp1 = l1;
Node temp2 = l2;
// If lengths differ, calculate the smaller
// Node and padd zeros for smaller Node and
// ensure both larger Node and smaller Node
// has equal length.
if (len1 != len2) {
lNode = len1 > len2 ? l1 : l2;
sNode = len1 > len2 ? l2 : l1;
sNode = paddZeros(sNode, Math.Abs(len1 - len2));
}
else {
// If both list lengths are equal, then
// calculate the larger and smaller list.
// If 5-6-7 & 5-6-8 are linked list, then
// walk through linked list at last Node
// as 7 < 8, larger Node is 5-6-8 and
// smaller Node is 5-6-7.
while (l1 != null && l2 != null) {
if (l1.data != l2.data) {
lNode = l1.data > l2.data ? temp1 : temp2;
sNode = l1.data > l2.data ? temp2 : temp1;
break;
}
l1 = l1.next;
l2 = l2.next;
}
}
// After calculating larger and smaller Node,
// call subtractLinkedListHelper which returns
// the subtracted linked list.
borrow = false;
return subtractLinkedListHelper(lNode, sNode);
}
// function to display the linked list
static void printList(Node head)
{
Node temp = head;
while (temp != null) {
Console.Write(temp.data + " ");
temp = temp.next;
}
}
// Driver code
public static void Main(String[] args)
{
Node head = new Node(1);
head.next = new Node(0);
head.next.next = new Node(0);
Node head2 = new Node(1);
LinkedList ob = new LinkedList();
Node result = ob.subtractLinkedList(head, head2);
printList(result);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to subtract smaller valued
// list from larger valued list and return
// result as a list.
var head; // head of list
var borrow;
/* Node Class */
class Node {
// Constructor to create a new node
constructor(d) {
this.data = d;
this.next = null;
}
}
/*
A utility function to get length of linked list
*/
function getLength(node) {
var size = 0;
while (node != null) {
node = node.next;
size++;
}
return size;
}
/*
A Utility that padds zeros in
front of the Node, with the given diff
*/
function paddZeros(sNode , diff) {
if (sNode == null)
return null;
var zHead = new Node(0);
diff--;
var temp = zHead;
while ((diff--) != 0) {
temp.next = new Node(0);
temp = temp.next;
}
temp.next = sNode;
return zHead;
}
/*
Subtract LinkedList Helper is a
recursive function, move till the last Node,
and subtract the digits and create the Node
and return the Node. If d1 < d2,
* we borrow the number from previous digit.
*/
function subtractLinkedListHelper(l1, l2) {
if (l1 == null && l2 == null && borrow == false)
return null;
var previous = subtractLinkedListHelper((l1 != null) ?
l1.next : null, (l2 != null) ? l2.next : null);
var d1 = l1.data;
var d2 = l2.data;
var sub = 0;
/*
if you have given the value to next
digit then reduce the d1 by 1
*/
if (borrow) {
d1--;
borrow = false;
}
/*
If d1 < d2, then borrow the number from
previous digit. Add 10 to d1 and set
borrow = true;
*/
if (d1 < d2) {
borrow = true;
d1 = d1 + 10;
}
/* subtract the digits */
sub = d1 - d2;
/* Create a Node with sub value */
var current = new Node(sub);
/* Set the Next pointer as Previous */
current.next = previous;
return current;
}
/*
This API subtracts two linked lists
and returns the linked list which shall
have the subtracted result.
*/
function subtractLinkedList(l1, l2) {
// Base Case.
if (l1 == null && l2 == null)
return null;
// In either of the case, get the lengths
// of both Linked list.
var len1 = getLength(l1);
var len2 = getLength(l2);
var lNode = null, sNode = null;
var temp1 = l1;
var temp2 = l2;
// If lengths differ, calculate the smaller
// Node and padd zeros for smaller Node and
// ensure both larger Node and smaller Node
// has equal length.
if (len1 != len2) {
lNode = len1 > len2 ? l1 : l2;
sNode = len1 > len2 ? l2 : l1;
sNode = paddZeros(sNode, Math.abs(len1 - len2));
}
else {
// If both list lengths are equal, then
// calculate the larger and smaller list.
// If 5-6-7 & 5-6-8 are linked list, then
// walk through linked list at last Node
// as 7 < 8, larger Node is 5-6-8 and
// smaller Node is 5-6-7.
while (l1 != null && l2 != null) {
if (l1.data != l2.data) {
lNode = l1.data > l2.data ? temp1 : temp2;
sNode = l1.data > l2.data ? temp2 : temp1;
break;
}
l1 = l1.next;
l2 = l2.next;
}
}
// After calculating larger and smaller Node,
// call subtractLinkedListHelper which returns
// the subtracted linked list.
borrow = false;
return subtractLinkedListHelper(lNode, sNode);
}
// function to display the linked list
function printList(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
}
// Driver program to test above
var head = new Node(1);
head.next = new Node(0);
head.next.next = new Node(0);
var head2 = new Node(1);
var result = subtractLinkedList(head, head2);
printList(result);
// This code contributed by aashish1995
</script>
Producción
0 9 9
Análisis de Complejidad:
- Complejidad temporal: O(n).
Como no se necesita un recorrido anidado de la lista enlazada. - Espacio Auxiliar: O(n).
Si se tiene en cuenta el espacio de pila recursivo, se necesita espacio O(n).
Este artículo es una contribución de Mu Ven . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA