簡介：
單鏈表中的每個結點不僅包含值，還包含鏈接到下一個結點的參考欄位，通過這種方式，單鏈表將所有結點按順序組織起來，下面是一個單鏈表的例子：
藍色箭頭顯示單個鏈接串列中的結點是如何組合在一起的，
節點結構：
1 // Definition for singly-linked list. 2 struct SinglyListNode { 3 int val; 4 SinglyListNode *next; 5 SinglyListNode(int x) : val(x), next(NULL) {} 6 };
設計鏈表：
設計鏈表的實作，您可以選擇使用單鏈表或雙鏈表，單鏈表中的節點應該具有兩個屬性：val 和 next，val 是當前節點的值，next 是指向下一個節點的指標/參考，如果要使用雙向鏈表，則還需要一個屬性 prev 以指示鏈表中的上一個節點，假設鏈表中的所有節點都是 0-index 的，
在鏈表類中實作這些功能：
- get(index)：獲取鏈表中第
index個節點的值，如果索引無效，則回傳-1， - addAtHead(val)：在鏈表的第一個元素之前添加一個值為
val的節點，插入后，新節點將成為鏈表的第一個節點， - addAtTail(val)：將值為
val的節點追加到鏈表的最后一個元素， - addAtIndex(index,val)：在鏈表中的第
index個節點之前添加值為val的節點，如果index等于鏈表的長度，則該節點將附加到鏈表的末尾，如果index大于鏈表長度，則不會插入節點，如果index小于0，則在頭部插入節點， - deleteAtIndex(index)：如果索引
index有效，則洗掉鏈表中的第index個節點，
示例：
MyLinkedList linkedList = new MyLinkedList(); linkedList.addAtHead(1); linkedList.addAtTail(3); linkedList.addAtIndex(1,2); //鏈表變為1-> 2-> 3 linkedList.get(1); //回傳2 linkedList.deleteAtIndex(1); //現在鏈表是1-> 3 linkedList.get(1); //回傳3
提示：
- 所有
val值都在[1, 1000]之內， - 操作次數將在
[1, 1000]之內， - 請不要使用內置的 LinkedList 庫，
代碼：
1 class MyLinkedList 2 { 3 public: 4 /** Initialize your data structure here. */ 5 MyLinkedList() : head(nullptr) {} 6 7 /** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */ 8 int get(int index) 9 { 10 if (head != nullptr) 11 { 12 Node *now = head; 13 int nownum = 0; 14 while (now->next != nullptr && nownum < index) 15 { 16 now = now->next; 17 nownum++; 18 } 19 if (nownum == index) 20 return now->val; 21 } 22 return -1; 23 } 24 25 /** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */ 26 void addAtHead(int val) 27 { 28 Node *temp = new Node(val); 29 temp->next = head; 30 head = temp; 31 } 32 33 /** Append a node of value val to the last element of the linked list. */ 34 void addAtTail(int val) 35 { 36 Node *temp = new Node(val); 37 if (head == nullptr) 38 head = temp; 39 else 40 { 41 Node *now = head; 42 while (now->next != nullptr) 43 now = now->next; 44 now->next = temp; 45 } 46 } 47 48 /** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */ 49 void addAtIndex(int index, int val) 50 { 51 Node *temp = new Node(val); 52 if (index <= 0) 53 { 54 temp->next = head; 55 head = temp; 56 } 57 else if (head != nullptr) 58 { 59 Node *pre = head; 60 int prenum = 0; 61 while (pre->next != nullptr && prenum < index - 1) 62 { 63 pre = pre->next; 64 prenum++; 65 } 66 if (prenum == index - 1) 67 { 68 temp->next = pre->next; 69 pre->next = temp; 70 } 71 } 72 } 73 74 /** Delete the index-th node in the linked list, if the index is valid. */ 75 void deleteAtIndex(int index) 76 { 77 if (head != nullptr) 78 { 79 if (index == 0) 80 { 81 Node *temp = head; 82 head = head->next; 83 delete temp; 84 } 85 else 86 { 87 Node *pre = head; 88 int prenum = 0; 89 while (pre->next != nullptr && prenum < index - 1) 90 { 91 pre = pre->next; 92 prenum++; 93 } 94 if (pre->next != nullptr && prenum == index - 1) 95 { 96 Node *temp = pre->next; 97 pre->next = temp->next; 98 delete temp; 99 } 100 } 101 } 102 } 103 104 private: 105 struct Node 106 { 107 int val; 108 struct Node *next; 109 Node(int x) : val(x), next(nullptr) {} 110 }; 111 struct Node *head; 112 }; 113 114 /** 115 * Your MyLinkedList object will be instantiated and called as such: 116 * MyLinkedList* obj = new MyLinkedList(); 117 * int param_1 = obj->get(index); 118 * obj->addAtHead(val); 119 * obj->addAtTail(val); 120 * obj->addAtIndex(index,val); 121 * obj->deleteAtIndex(index); 122 */
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/205851.html
標籤：其他
上一篇：不用加減乘除做加法