Code & Func

今天的题目是707. Design Linked List

设计链表的实现。您可以选择使用单链表或双链表。单链表中的节点应该具有两个属性：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
MyLinkedList linkedList = new MyLinkedList();
2
linkedList.addAtHead(1);
3
linkedList.addAtTail(3);
4
linkedList.addAtIndex(1,2);   //链表变为1-> 2-> 3
5
linkedList.get(1);            //返回2
6
linkedList.deleteAtIndex(1);  //现在链表是1-> 3
7
linkedList.get(1);            //返回3

提示：

所有val值都在 [1, 1000] 之内。
操作次数将在 [1, 1000] 之内。
请不要使用内置的 LinkedList 库。

多说无益，给个双链表的题解：

1
struct MyLinkedNode {
2
    int val;
3
    MyLinkedNode *prev, *next;
4
    MyLinkedNode(int v = -1):val(v),prev(this),next(this){}
5
    ~MyLinkedNode() {
6
        prev->next = next;
7
        next->prev = prev;
8
    }
9
    void ConnectNext(MyLinkedNode* node) {
10
        node->next = next;
11
        next->prev = node;
12
        node->prev = this;
13
        next = node;
14
    }
15

59 collapsed lines
16
    void ConnectPrev(MyLinkedNode* node) {
17
        node->prev = prev;
18
        prev->next = node;
19
        node->next = this;
20
        prev = node;
21
    }
22
};
23

24
class MyLinkedList {
25
public:
26
    MyLinkedNode head;
27
    MyLinkedList() : head(0) {
28
        // head.val == size
29
    }
30

31
    MyLinkedNode* getNode(int index) {
32
        // assert index >= 0 && index < size;
33
        if (index < 0 || index >= head.val) return nullptr;
34
        auto p = head.next;
35
        for (int i = 0; i < index; i++) {
36
            p = p->next;
37
        }
38
        return p;
39
    }
40

41
    int get(int index) {
42
       auto p = getNode(index);
43
       return p ? p->val : -1;
44
    }
45

46
    void addAtHead(int val) {
47
        head.ConnectNext(new MyLinkedNode(val));
48
        head.val++;
49
    }
50

51
    void addAtTail(int val) {
52
        head.ConnectPrev(new MyLinkedNode(val));
53
        head.val++;
54
    }
55

56
    void addAtIndex(int index, int val) {
57
        if (index == head.val) addAtTail(val);
58
        else if (index > head.val) return;
59
        else if (index < 0) addAtHead(val);
60
        else {
61
            auto p = getNode(index);
62
            p->ConnectPrev(new MyLinkedNode(val));
63
            head.val++;
64
        }
65
    }
66

67
    void deleteAtIndex(int index) {
68
        auto p = getNode(index);
69
        if (p) {
70
            delete p;
71
            head.val--;
72
        }
73
    }
74
};