aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-01-14 12:47:05 -0700
committerJack Sangdahl <[email protected]>2025-01-14 12:47:05 -0700
commit739d4b1bff93a46887828a958d85c4a0a0bd6c71 (patch)
treeda4a2f3cb967afd1e5de4d679b2a4a2e52848cb7
parentb4e04c3e1da4d6ab0b439b71622a32d61fb25c9d (diff)
downloadleetcode-739d4b1bff93a46887828a958d85c4a0a0bd6c71.tar.gz
leetcode-739d4b1bff93a46887828a958d85c4a0a0bd6c71.zip
707. design linked list
-rw-r--r--design_linked_list.c103
-rw-r--r--design_linked_list.py107
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))