leetcode

0 class MyLinkedList {

1 struct Node {

2 int val;

3 Node *next;

4

5 Node(int val, Node *next = nullptr) : val(val), next(next) {}

6 };

7

8 Node *head = nullptr, *tail = nullptr;

9 int size = 0;

10

11 public:

12 MyLinkedList() {}

13

14 int get(int index) {

15 if (index >= size) return -1;

16

17 Node *p = head;

18 while (index--)

19 p = p->next;

20 return p->val;

21 }

22

23 void addAtHead(int val) {

24 if (!head)

25 head = tail = new Node(val);

26 else

27 head = new Node(val, head);

28 size++;

29 }

30

31 void addAtTail(int val) {

32 if (!head)

33 head = tail = new Node(val);

34 else

35 tail = tail->next = new Node(val);

36 size++;

37 }

38

39 void addAtIndex(int index, int val) {

40 if (index > size) return;

41

42 Node *p = head;

43 size++;

44

45 if (index == 0) {

46 addAtHead(val);

47 return;

48 }

49

50 while (--index)

51 p = p->next;

52 p->next = new Node(val, p->next);

53 if (p == tail) tail = p->next;

54 }

55

56 void deleteAtIndex(int index) {

57 if (index >= size) return;

58

59 Node *t, *p;

60 size--;

61

62 if (index == 0) {

63 cout << "head" << endl;

64 t = head;

65 head = head->next;

66 delete t;

67 return;

68 }

69

70 p = head;

71 while (--index)

72 p = p->next;

73

74 t = p->next;

75 p->next = p->next->next;

76 if (t == tail) tail = p;

77 delete t;

78 }

79 };