代码随想录算法训练营第三天 |移除链表元素(LeetCode203)、设计链表(LeetCode707)、 反转链表 (LeetCode206)

引用说明

文档讲解：代码随想录

移除链表元素(LeetCode203)

?1.不加虚拟头结点

分两种情况进行：

1、需要删除头结点：

while(head != NULL && head->val == val){
            ListNode* temp = head;
            head = head->next;
            delete temp;
        }

2、头结点不需要删除，只需删除后面的节点：

ListNode * cur = head;
        while(cur != NULL && cur->next != NULL){
            if(cur->next->val == val){
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }else{
                cur = cur->next;
            }
        }

2.加虚拟头结点?

?同不需要删除头结点的方法

ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyhead = new ListNode(0);
        dummyhead->next = head;
        ListNode* cur = dummyhead;
        while (cur != NULL && cur->next != NULL)
        {
            if(cur->next->val == val){
                ListNode* temp = cur->next;
                cur->next = cur->next->next;
                delete temp;
            }else{
                cur = cur->next;
            }
        }
        return dummyhead->next;
    }

2.头部插入节点

注意：要将链表长度+1

void addAtHead(int val) {
        LinkedNode* cur = new LinkedNode(0);
        cur->val = val;
        cur->next = _dummyhead->next;
        _dummyhead->next = cur;
        _size++;
    }

3.尾部插入节点

注意：要将链表长度+1

void addAtTail(int val) {
        LinkedNode* tail = _dummyhead;
        while(tail->next != NULL){
            tail = tail->next;
        }
        LinkedNode* p = new LinkedNode(val);
        p->next = tail->next;
        tail->next = p;
        tail = p;
        _size++;
    }

4.在第n个节点前插入节点

注意：判断index的范围是否合法；

? ? ? ? ? ?链表长度+1。

    //按位序插入
    void addAtIndex(int index, int val) {
        if(index > _size) return;
        if(index < 0) index = 0;  
        LinkedNode* cur = _dummyhead;
        while (index--)
        {
            cur = cur->next;
        }
        LinkedNode* temp = new LinkedNode(val);
        temp->next = cur->next;
        cur->next = temp;
        _size++;
    }

5.删除第n个节点?

注意：判断index的范围的合法性；

? ? ? ? ? ?链表长度-1。

    void deleteAtIndex(int index) {
        if (index >= _size || index < 0) {
            return;
        }
        LinkedNode* cur = _dummyhead;
        while (index--)
        {
            cur = cur->next;
        }
        LinkedNode* temp = cur->next;
        cur->next = cur->next->next;
        delete temp;
        temp=nullptr;
        _size--;
    }

反转链表(LeetCode206)

1.头插法

ListNode* reverseList(ListNode* head) {
        int count = 0;
        ListNode* _dummyHead = new ListNode(0);
        _dummyHead->next = head;
        ListNode* tail = _dummyHead;
        while(tail->next != NULL){
            tail = tail->next;
            count++;
        }
        ListNode* cur = _dummyHead->next;
         while(cur != NULL && cur->next != NULL){
            ListNode* p = cur->next;
            cur->next = cur->next->next;
            p->next = _dummyHead->next;
            _dummyHead->next = p;
        }
        return _dummyHead->next;
    }

2.双指针逆置

注意：要申请一个临时指针temp记录cur的下一个位置

ListNode* reverseList(ListNode* head) {
        ListNode* pre = NULL;
        ListNode* cur = head;
        while(cur != NULL){
            ListNode* temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }

注意： 先移动pre再cur

?

3.递归法（类比双指针）?

注意：类比双指针的思想

 ListNode* reverseList(ListNode* head) {
        return reverse(NULL,head);
    }

    ListNode* reverse(ListNode* pre, ListNode* cur) {
        if(cur == NULL) return pre;
        ListNode* temp = cur->next;
        cur->next = pre;
         return reverse(cur,temp);
    }