文章目錄

• • 1. 設(shè)計(jì)一個(gè)單鏈表
  • 2. 雙向鏈表

1. 設(shè)計(jì)一個(gè)單鏈表

在鏈表類中實(shí)現(xiàn)這些功能：

get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無效，則返回-1。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長(zhǎng)度，則不會(huì)插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/design-linked-list
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

class node { public:int val;node *next;node(int v):val(v),next(NULL) {} }; class MyLinkedList {node *head, *tail;int len; public:/** Initialize your data structure here. */MyLinkedList() {head = tail = NULL;len = 0;}/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */int get(int index) {if(index >= len || index < 0)return -1;node *cur = head;while(index--)cur = cur->next;return cur->val;}/** 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. */void addAtHead(int val) { node *h = new node(val);h->next = head;head = h;if(len == 0)tail = head;++len;}/** Append a node of value val to the last element of the linked list. */void addAtTail(int val) {node *t = new node(val);if(len == 0){head = tail = t;}else{tail->next = t;tail = t;}++len; }/** 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. */void addAtIndex(int index, int val) {if(index == len)addAtTail(val);else if(index <= 0)addAtHead(val);else if(index > len)return;else{node *cur = head;while(--index)cur = cur->next;node *newNode = new node(val);newNode->next = cur->next;cur->next = newNode;++len;}}/** Delete the index-th node in the linked list, if the index is valid. */void deleteAtIndex(int index) {if(index >= len || index < 0)return;--len;node *virtualheadNode, *del, *cur;virtualheadNode = new node(0);virtualheadNode->next = head;cur = virtualheadNode;while(index--){cur = cur->next;}del = cur->next;cur->next = cur->next->next;delete del;head = virtualheadNode->next;if(cur->next == NULL)tail = cur;delete virtualheadNode;} };

2. 雙向鏈表

class node { public:int val;node *next;node *prev;node(int v):val(v),next(NULL),prev(NULL) {} }; class MyLinkedList {node *head, *tail;int len; public:/** Initialize your data structure here. */MyLinkedList() {head = tail = NULL;len = 0;}/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */int get(int index) {if(index >= len || index < 0)return -1;node *cur = head;while(index--)cur = cur->next;return cur->val;}/** 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. */void addAtHead(int val) { node *h = new node(val);h->next = head;head = h;if(len == 0)tail = head;++len;}/** Append a node of value val to the last element of the linked list. */void addAtTail(int val) {node *t = new node(val);if(len == 0){head = tail = t;}else{tail->next = t;t->prev = tail;tail = t;}++len; }/** 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. */void addAtIndex(int index, int val) {if(index == len)addAtTail(val);else if(index <= 0)addAtHead(val);else if(index > len)return;else{node *cur = head;while(--index)cur = cur->next;node *newNode = new node(val);newNode->next = cur->next;newNode->prev = cur;cur->next->prev = newNode;cur->next = newNode;++len;}}/** Delete the index-th node in the linked list, if the index is valid. */void deleteAtIndex(int index) {if(index >= len || index < 0)return;--len;node *virtualheadNode, *del, *cur;virtualheadNode = new node(0);virtualheadNode->next = head;head->prev = virtualheadNode;cur = virtualheadNode;while(index--){cur = cur->next;}del = cur->next;cur->next = cur->next->next;if(del->next) del->next->prev = cur;delete del;head = virtualheadNode->next;if(cur->next == NULL)tail = cur;delete virtualheadNode;} };

總結(jié)

以上是生活随笔為你收集整理的LeetCode 707. 设计链表（List）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。