链表

这类题不难，掌握链表的遍历即可。

例题

707. 设计链表

class MyLinkedList {
public:

    // 定义链表节点结构体
    struct LinkedNode
    {
        int val;
        LinkedNode* next;
        LinkedNode(int val):val(val),next(nullptr){};
    };
    
    // 初始化链表
    MyLinkedList() {
        _dum = new LinkedNode(0);
        _size = 0;
    }
    
    // 获取到底index个节点数值，如果index是非法数值直接返回-1，
    // 注意index是从0开始的，第0个节点就是头结点
    int get(int index) {
        if(index>(_size-1) || index<0) return -1;
        LinkedNode* p = _dum->next;
        while(index--){
            p = p->next;
        }
        return p->val;
    }
    
    void addAtHead(int val) {
        LinkedNode* node = new LinkedNode(val);
        node->next = _dum->next;
        _dum->next = node;
        _size++;
    }
    
    void addAtTail(int val) {
        LinkedNode* node = new LinkedNode(val);
        LinkedNode* p = _dum;
        while(p->next!=nullptr){
            p = p->next;
        }
        p->next = node;
        _size++;
    }
    
    void addAtIndex(int index, int val) {
        LinkedNode* node = new LinkedNode(val);
        if(index>_size || index<0) return;
        LinkedNode* p = _dum;
        while(index--){
            p = p->next;
        }
        node->next = p->next;
        p->next = node;
        _size++;
    }

    void deleteAtIndex(int index) {
        if(index>=_size || index<0) return;
        LinkedNode* p = _dum;
        while(index--){
            p = p->next;
        }
        p->next = p->next->next;
        _size--;
    }

private:
    LinkedNode* _dum;
    int _size;
};

203. 移除链表元素

ListNode* removeElements(ListNode* head, int val) {
	if(head==nullptr) return head;
	ListNode* dum = new ListNode(-1);
	dum->next = head;
	ListNode * p = dum;
	while(p->next!=nullptr){
		if(p->next->val==val){
			p->next = p->next->next;
		}
		else{
			p = p->next;
		}
	}
	return dum->next;
}

206. 反转链表

解法一：递归

ListNode* reverseList(ListNode* head) {
	if(head==nullptr || head->next==nullptr) return head;
	ListNode* nxt = reverseList(head->next);
	head->next->next = head;
	head->next = nullptr;
	return nxt;
}

解法二：迭代

ListNode* reverseList(ListNode* head) {
	if(head==nullptr || head->next==nullptr) return head;
	ListNode* pre = nullptr, *cur = head;
	while(cur!=nullptr){
		ListNode* tmp = cur->next;
		cur->next = pre;
		pre = cur;
		cur = cur->next;
	}
	return pre;
}