首页 > 编程语言 >代码随想录算法训练营day03|203.移除链表元素,707.设计链表,206.反转链表

代码随想录算法训练营day03|203.移除链表元素,707.设计链表,206.反转链表

时间:2024-08-03 23:50:12浏览次数:17  
标签:current head ListNode val int 随想录 next 链表 移除

203.移除链表元素

题目链接:https://leetcode.cn/problems/remove-linked-list-elements/description/

我的代码(分头节点和中间节点两种情况操作):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head != nullptr && head->val == val) {
            ListNode* q = head;
            head = head->next;
            delete q;
        }
        ListNode* p = head;
        while (p != nullptr && p->next != nullptr) {
            if (p->next->val == val) {
                ListNode* q = p->next;
                p->next = q->next;
                delete q;
            } else
                p = p->next;
        }
        return head;
    }
};

头节点操作:直接后移头节点并将原来的头节点内存释放。
中间节点操作:检测到当前节点后一个节点的数据域等于索引值时,将当前节点的指针域指向后一个节点的后一个节点,然后释放后一个节点的内存,否则后移当前节点。

虚拟头节点(所有节点按一种方法操作):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummy_head = new ListNode;
        dummy_head->next = head;
        ListNode* current = dummy_head;
        while (current->next != nullptr) {
            if (current->next->val == val) {
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp;
            } else
                current = current->next;
        }
        head = dummy_head->next;
        delete dummy_head;
        return head;
    }
};

在原链表的头节点之前再加一个实际上不存储数据的虚拟头节点,方便操作。

707.设计链表

题目链接:https://leetcode.cn/problems/design-linked-list/description/

我的代码:

class MyLinkedList {
public:
    struct LinkedList {
        int val;
        struct LinkedList* next;
        LinkedList(int val) : val(val), next(nullptr) {}
    };
    MyLinkedList() {
        dummy_head = new LinkedList(0);
        size = 0;
    }

    int get(int index) {
        if (index < size && index >= 0) {
            LinkedList* p = dummy_head->next;
            while (index > 0) {
                index--;
                p = p->next;
            }
            return p->val;
        } else
            return -1;
    }

    void addAtHead(int val) {
        LinkedList* p = new LinkedList(val);
        p->next = dummy_head->next;
        dummy_head->next = p;
        size++;
    }

    void addAtTail(int val) {
        LinkedList* p = new LinkedList(val);
        LinkedList* q = dummy_head;
        int length = size;
        while (length > 0) {
            length--;
            q = q->next;
        }
        q->next = p;
        p->next = nullptr;
        size++;
    }

    void addAtIndex(int index, int val) {
        if (index >= 0 && index < size) {
            LinkedList* p = new LinkedList(val);
            LinkedList* q = dummy_head;
            while (index > 0) {
                index--;
                q = q->next;
            }
            p->next = q->next;
            q->next = p;
            size++;
        } else if (index == size) {
            LinkedList* p = new LinkedList(val);
            LinkedList* q = dummy_head;
            while (index > 0) {
                index--;
                q = q->next;
            }
            q->next = p;
            p->next = nullptr;
            size++;
        }
    }

    void deleteAtIndex(int index) {
        LinkedList* p = dummy_head;
        if (index < size && index >= 0) {
            while (index > 0) {
                index--;
                p = p->next;
            }
            LinkedList* q = p->next;
            p->next = q->next;
            delete q;
            size--;
        }
    }

private:
    LinkedList* dummy_head;
    int size;
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

206.反转链表

题目链接:https://leetcode.cn/problems/reverse-linked-list/description/

双指针解法:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre = nullptr;
        ListNode* current = head;
        while (current != nullptr) {
            ListNode* temp = current->next;
            current->next = pre;
            pre = current;
            current = temp;
        }
        return pre;
    }
};

pre:开始定义为头节点前的空指针。
current:开始定义为头节点。
每次循环使用temp暂存current的next节点,然后使current的next指针指向pre,pre和current都后移,最后当current指向尾节点后的空指针时结束循环,返回当前真正头节点pre。

递归解法:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) { return reverse(nullptr, head); }
    ListNode* reverse(ListNode* pre, ListNode* current) {
        if (current == nullptr)
            return pre;
        ListNode* temp = current->next;
        current->next = pre;
        return reverse(current, temp);
    }
};

与双指针解法思路相同。

标签:current,head,ListNode,val,int,随想录,next,链表,移除
From: https://www.cnblogs.com/kurumaruq/p/18339958

相关文章

  • Linux内核-内核链表
    1内核链表内核链表本质就是一个双向循环链表:链表的实现仅用一个include/linux/list.h实现。内核链表有别于传统链表就在节点本身不包含数据域,只包含指针域。故而可以很灵活的拓展数据结构。使用时包含在用户数据结构内部。1.1内核链表结构体structlist_head{struct......
  • leetcode 021:删除链表的倒数第 N 个结点
    LCR021.删除链表的倒数第N个结点给定一个链表,删除链表的倒数第 n 个结点,并且返回链表的头结点。示例1:输入:head=[1,2,3,4,5],n=2输出:[1,2,3,5]示例2:输入:head=[1],n=1输出:[]示例3:输入:head=[1,2],n=1输出:[1]structListNode*removeNthF......
  • C++实现静态链表
    #include<iostream>usingnamespacestd;//定义静态链表的最大容量constintMAX_SIZE=100;//节点类classNode{public:intdata;//节点存储的数据intnext;//节点指向下一个节点的索引(在数组中的位置)//默认构造函数Node():data(0......
  • 代码随想录 day 44 最长公共子序列 | 不相交的线 | 最大子序和 | 判断子序列
    最长公共子序列最长公共子序列解题思路本题dp数组的含义是最长公共序列,而后同时遍历两个字符串,遇到相同的字母是公共子序列+1,否则取两个字符串的公共子序列中较长的一个。知识点动态规划,子序列心得没有想到比较两个字符串的公共子序列。我自己是遇到相同字母时将所有后续的......
  • 链表part01
    今天是8月2日,学习了链表的基础知识。题目主要是链表的基础操作和反转链表,注意虚拟头节点的使用、next的顺序和tmp的灵活使用。1.移除元素题目:给一个链表的头节点head和整数val,请删除链表中所有满足Node.val==val的节点,并返回新的头节点。删除的方法,cur指针挨个遍......
  • 结构体与共用体,链表的学习
    结构体定义        C语言允许用户自己定义一种数据结构,称为结构体。        声明一个结构体类型一般形式为:                strcut 结构体名                {                    成员列表......
  • 代码随想录算法训练营Day18 | Leetcode 530 二叉搜索树的最小绝对差 Leetcode 236 二
    前言今天有一道题目没写,二叉搜索树中的众数,有点太难理解了,先放一放。Leetcode530二叉搜索树的最小绝对差题目链接:530.二叉搜索树的最小绝对差-力扣(LeetCode)代码随想录题解:代码随想录(programmercarl.com)思路:二叉搜索树的性质是中序遍历为升序的,所以我们想找最小绝......
  • 代码随想录day32 || 509斐波那契数列 70爬楼梯 746使用最小花费爬楼梯
    509斐波那契数列力扣题目链接题目描述:斐波那契数 (通常用 F(n) 表示)形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:F(0)=0,F(1) =1F(n)=F(n-1)+F(n-2),其中n>1给定 n ,请计算 F(n) 。代码1......
  • 代码随想录day31|| 56合并区间 738 递增数字
    56合并区间 力扣题目链接题目描述:以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i]=[starti,endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。示例1:输入:intervals=[[1,3],[2,6],[8,10],[1......
  • 141.环形链表
    给你一个链表的头节点 head ,判断链表中是否有环。如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。注意:pos 不作为参数进行传递 。仅仅是为......