算法训练 Leetcode 203、206、707

203.移除链表元素

以为头结点是空的，里面只存着下一个结点的地址。

注意空指针检查：p!=NULL;

class Solution
{
public:
    ListNode *removeElements(ListNode *head, int val)
    {
        ListNode *p = head;
        while (p != nullptr && p->next != nullptr)
        {
            if (p->next->val == val)
            {
                ListNode *q = p->next;
                p->next = p->next->next;
                delete q;
            }
            else
                p = p->next;
        }
        if (head != nullptr && head->val == val)
        {
            ListNode *p = head;
            head = head->next;
            delete p;
        }
        return head;
    }
};

707.设计链表

指针总是出错，关键在于

LinkNode* p = poorhead;还是LinkNode* p = poorhead->next;

题解

#include <iostream>
using namespace std;
class MyLinkedList
{

public:
    // 定义链表结构体
    struct LinkNode
    {
        int val;
        LinkNode *next;
        LinkNode(int val) : val(val), next(nullptr) {}
    };

    // 链表初始化
public:
    MyLinkedList()
    {
        poorhead = new LinkNode(0);
        _size = 0;
    }

    // 获取链表中下标为index的节点的值
    int get(int index)
    {
        if (index < 0 || index >= _size)
            return -1;
        LinkNode *p = poorhead->next;
        while (index--)
        {
            p = p->next;
        }
        return p->val;
    }

    // 将值val结点插入到第一个元素之前
    void addAtHead(int val)
    {
        LinkNode *p = new LinkNode(val);
        p->next = poorhead->next;
        poorhead->next = p;
        _size++;
    }

    // 将值val结点追加作为链表最后一个元素*******
    void addAtTail(int val)
    {
        // LinkNode* p = poorhead->next;******
        LinkNode *p = poorhead;
        while (p != nullptr && p->next != nullptr)
        {
            p = p->next;
        }
        // LinkNode* newnode = new LinkNode(val);
        // p ->next = newnode;
        p->next = new LinkNode(val);
        _size++;
    }

    // 将val值结点插入到链表中下表为index的结点之前，如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
    void addAtIndex(int index, int val)
    {
        if (index > _size)
            return;
        if (index < 0)
            index = 0;
        LinkNode *newnode = new LinkNode(val);
        LinkNode *p = poorhead;
        while (index--)
        {
            p = p->next;
        }
        newnode->next = p->next;
        p->next = newnode;
        _size++;
    }

    // 如果下标有效，则删除链表中下标为 index 的节点
    void deleteAtIndex(int index)
    {
        if (index >= 0 && (index - _size) < 0)
        {
            LinkNode *p = poorhead;
            while (index--)
            {
                p = p->next;
            }
            LinkNode *q = p->next;
            p->next = p->next->next;
            delete q;
            q == nullptr;
            _size--;
        };
    }
    void printLinkedList()
    {
        LinkNode *cur = poorhead;
        while (cur->next != nullptr)
        {
            cout << cur->next->val << " ";
            cur = cur->next;
        }
        cout << _size << endl;
    }

private:
    int _size;
    LinkNode *poorhead;
};

int main()
{
    MyLinkedList list;
    list.addAtTail(1);
    list.get(0);

    return 0;
}

// 指针指针指针指针！！！！！

206.反转链表

相对简单，复习了双指针和递归

题解

// 双指针

class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        ListNode *temp;
        ListNode *pre = head;
        ListNode *cur = NULL;
        while (pre)
        {
            temp = pre->next;
            pre->next = cur;
            cur = pre;
            pre = temp;
            ;
        }
        return cur;
    }
};

// 递归
class Solution
{
public:
    ListNode *reverse(ListNode *pre, ListNode *cur)
    {
        if (pre == NULL)
            return cur;
        ListNode *temp = pre->next;
        pre->next = cur;
        return reverse(temp, pre);
    }
    ListNode *reverseList(ListNode *head)
    {
        return reverse(head, NULL);
    }
};