本文共 3197 字，大约阅读时间需要 10 分钟。
题目：
设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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 个节点。/* 1、链表节点结构体自己定义的 2、在privite中定义了两个私有变量。一个大小size，一个是虚拟头结点，便于操作 3、注意私有变量的定义，在前面加了一条下划线 4、这道题要注意 index 是从0开始的，所以在处理细节时要注意，比如在删除函数中*/class MyLinkedList {public: // 定义链表节点结构体 struct ListNode { int val; ListNode* next; ListNode(int value) :val(value), next(nullptr) {} }; // 初始化链表 MyLinkedList() { _dummyHead = new ListNode(0); _size = 0; } // 获取链表中第 index 个节点的值 int get(int index) { int count = 0; ListNode* pNode = _dummyHead; while (pNode->next) { if (count == index) { return pNode->next->val; } else { pNode = pNode->next; ++count; } } return -1; } // 在链表的第一个元素之前添加一个值为 val 的节点。 void addAtHead(int val) { ListNode* newHead = new ListNode(val); ListNode* pTemp = _dummyHead->next; _dummyHead->next = newHead; newHead->next = pTemp; ++_size; } // 将值为 val 的节点追加到链表的最后一个元素。 void addAtTail(int val) { ListNode* newTail = new ListNode(val); ListNode* pNode = _dummyHead; while (pNode->next) pNode = pNode->next; pNode->next = newTail; ++_size; } // 在链表中的第 index 个节点之前添加值为 val 的节点。 void addAtIndex(int index, int val) { ListNode* newNode = new ListNode(val); ListNode* pNode = _dummyHead; int count = 0; if (index <= _size) { while (count<=_size) { if ((count == index&&count!=_size)|| index < 0) { ListNode* pTemp = pNode->next; pNode->next = newNode; newNode->next = pTemp; ++_size; break; } else if (count == _size) { pNode->next = newNode; ++_size; break; } else { pNode = pNode->next; ++count; } } } } // 如果索引 index 有效，则删除链表中的第 index 个节点。 void deleteAtIndex(int index) { ListNode* pNode = _dummyHead; int count = 0; if(index>=_size||index<0) { return; } // 这里写成 --index就出错了~ // 注意index是从0开始的, // 因为是从0开始，所以不能用--index // 因为不然第0个节点就会失败了 while (index--) { pNode = pNode->next; } ListNode* pTemp = pNode->next; pNode->next=pNode->next->next; delete pTemp; --_size; }private: int _size; ListNode* _dummyHead;}; 转载地址：http://nhpsz.baihongyu.com/