diff options
author | Jack Sangdahl <[email protected]> | 2025-01-14 12:47:05 -0700 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-01-14 12:47:05 -0700 |
commit | 739d4b1bff93a46887828a958d85c4a0a0bd6c71 (patch) | |
tree | da4a2f3cb967afd1e5de4d679b2a4a2e52848cb7 | |
parent | b4e04c3e1da4d6ab0b439b71622a32d61fb25c9d (diff) | |
download | leetcode-739d4b1bff93a46887828a958d85c4a0a0bd6c71.tar.gz leetcode-739d4b1bff93a46887828a958d85c4a0a0bd6c71.zip |
707. design linked list
-rw-r--r-- | design_linked_list.c | 103 | ||||
-rw-r--r-- | design_linked_list.py | 107 |
2 files changed, 210 insertions, 0 deletions
diff --git a/design_linked_list.c b/design_linked_list.c new file mode 100644 index 0000000..f1e78be --- /dev/null +++ b/design_linked_list.c @@ -0,0 +1,103 @@ +// 707. Design Linked List +#include "leetcode.h" + +/* + * design your implementation of the linked list. you can choose to use a singly + * or doubly linked list. a node in a singly linked list should have two + * attributes: 'val' and 'next'. 'val' is the value of the current node, and + * 'next' is a pointing/reference to the next code. if you want to use the + * doubly linked list, you will need one more attribute 'prev' to indicate the + * previous node in the linked list. assume all nodes in the linked list are + * 0-indexed to indicate the previous node in the linked list. assume all nodes + * in the linked list are 0-indexed. + */ + +typedef struct List { + int val; + struct List *next; +} MyLinkedList; + +MyLinkedList *myLinkedListCreate() { + MyLinkedList *obj = (MyLinkedList *)malloc(sizeof(MyLinkedList)); + obj->val = -1; + obj->next = NULL; + return obj; +} + +int myLinkedListGet(MyLinkedList *obj, int index) { + obj = obj->next; + int cnt = 0; + while (obj) { + if (cnt == index) + return obj->val; + cnt++; + obj = obj->next; + } + return -1; +} + +void myLinkedListAddAtHead(MyLinkedList *obj, int val) { + MyLinkedList *tmp = (MyLinkedList *)malloc(sizeof(MyLinkedList)); + tmp->val = val; + tmp->next = obj->next; + obj->next = tmp; +} + +void myLinkedListAddAtTail(MyLinkedList *obj, int val) { + while (obj && obj->next) + obj = obj->next; + MyLinkedList *tmp = (MyLinkedList *)malloc(sizeof(MyLinkedList)); + tmp->val = val; + tmp->next = NULL; + obj->next = tmp; +} + +void myLinkedListAddAtIndex(MyLinkedList *obj, int index, int val) { + int cnt = 0; + MyLinkedList *tmp = obj; + while (tmp) { + if (cnt == index) { + MyLinkedList *curr = (MyLinkedList *)malloc(sizeof(MyLinkedList)); + curr->val = val; + curr->next = tmp->next; + tmp->next = curr; + break; + } + cnt++; + tmp = tmp->next; + } +} + +void myLinkedListDeleteAtIndex(MyLinkedList *obj, int index) { + int cnt = 0; + MyLinkedList *curr = obj->next, *pre = obj; + while (curr) { + if (cnt == index) { + pre->next = curr->next; + free(curr); + return; + } + cnt++; + pre = curr; + curr = curr->next; + } +} + +void myLinkedListFree(MyLinkedList *obj) { + while (obj) { + MyLinkedList *tmp = obj; + obj = obj->next; + free(tmp); + } +} + +int main() { + MyLinkedList *obj = myLinkedListCreate(); + myLinkedListAddAtHead(obj, 1); + myLinkedListAddAtTail(obj, 3); + myLinkedListAddAtIndex(obj, 1, 2); + printf("%d\n", myLinkedListGet(obj, 1)); // expect: 2 + myLinkedListDeleteAtIndex(obj, 1); + printf("%d\n", myLinkedListGet(obj, 1)); // expect: 3 + myLinkedListFree(obj); +} diff --git a/design_linked_list.py b/design_linked_list.py new file mode 100644 index 0000000..0ef176d --- /dev/null +++ b/design_linked_list.py @@ -0,0 +1,107 @@ +# 707. Design Linked List + +""" +design your implementation of the linked list. you can choose to use a singly +or doubly linked list. a node in a singly linked list should have two +attributes: 'val' and 'next'. 'val' is the value of the current node, and +'next' is a pointing/reference to the next code. if you want to use the +doubly linked list, you will need one more attribute 'prev' to indicate the +previous node in the linked list. assume all nodes in the linked list are +0-indexed to indicate the previous node in the linked list. assume all nodes +in the linked list are 0-indexed. +""" + + +class Node(object): + def __init__(self, val): + self.val = val + self.next = None + + +class MyLinkedList(object): + def __init__(self): + self.head = None + self.size = 0 + + def get(self, index): + """ + :type index: int + :rtype: int + """ + if index < 0 or index >= self.size: + return -1 + if self.head is None: + return -1 + curr = self.head + for i in range(index): + curr = curr.next + return curr.val + + def addAtHead(self, val): + """ + :type val: int + :rtype: None + """ + node = Node(val) + node.next = self.head + self.head = node + self.size += 1 + + def addAtTail(self, val): + """ + :type val: int + :rtype: None + """ + curr = self.head + if curr is None: + self.head = Node(val) + else: + while curr.next is not None: + curr = curr.next + curr.next = Node(val) + self.size += 1 + + def addAtIndex(self, index, val): + """ + :type index: int + :type val: int + :rtype: None + """ + if index < 0 or index > self.size: + return + if index == 0: + self.addAtHead(val) + else: + curr = self.head + for i in range(index - 1): + curr = curr.next + node = Node(val) + node.next = curr.next + curr.next = node + self.size += 1 + + def deleteAtIndex(self, index): + """ + :type index: int + :rtype: None + """ + if index < 0 or index >= self.size: + return + curr = self.head + if index == 0: + self.head = curr.next + else: + for i in range(index - 1): + curr = curr.next + curr.next = curr.next.next + self.size -= 1 + + +if __name__ == "__main__": + obj = MyLinkedList() + obj.addAtHead(1) + obj.addAtTail(3) + obj.addAtIndex(1, 2) + print(obj.get(1)) + obj.deleteAtIndex(1) + print(obj.get(1)) |