707. 设计链表

707. 设计链表

详见主站的链表笔记。

主要笔记的实现是偏考试的做法。在这种做题的地方可以加一个size数据成员，记录链表的长度，这样在判index合不合法的时候就不用遍历一遍了。

提交代码：

class MyLinkedList {
  private:
	struct LNode {
		int val;
		LNode *next;
	};
	LNode *head;
	int size;

  public:
	MyLinkedList()
	{
		head = (LNode *)malloc(sizeof(LNode));
		head->next = NULL;
		size = 0;
	}

	int get(int index)
	{
		if (index < 0 || index > size - 1) {
			return -1;
		}
		LNode *p = head;
		int pos = -1;
		while (p != NULL && pos < index) {
			p = p->next;
			pos++;
		}
		if (p == NULL) {
			return -1;
		}
		else {
			return p->val;
		}
	}

	void addAtHead(int val)
	{
		LNode *p = head;
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->val = val;
		s->next = p->next;
		p->next = s;
		size++;
	}

	void addAtTail(int val)
	{
		LNode *p = head;
		while (p->next != NULL) {
			p = p->next;
		}
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->val = val;
		s->next = p->next;
		p->next = s;
		size++;
	}

	void addAtIndex(int index, int val)
	{
		if (index < 0 || index > size) {
			return;
		}
		LNode *p = head;
		int pos = -1;
		while (p->next != NULL && pos < index - 1) {
			p = p->next;
			pos++;
		}
		LNode *s = (LNode *)malloc(sizeof(LNode));
		s->val = val;
		s->next = p->next;
		p->next = s;
		size++;
	}

	void deleteAtIndex(int index)
	{
		if (index < 0 || index > size - 1) {
			return;
		}
		LNode *p = head;
		int pos = -1;
		while (p->next->next != NULL && pos < index - 1) {
			p = p->next;
			pos++;
		}
		LNode *q = p->next;
		p->next = q->next;
		free(q);
		size--;
	}
};