工作室网站建设要多大内存,电子书新手学做网站,jquery 案例网站,教育培训网站案例目录 203. 移除链表元素
707、设计链表
206.反转链表 203. 移除链表元素
题意#xff1a;删除链表中等于给定值 val 的所有节点。
示例 1#xff1a; 输入#xff1a;head [1,2,6,3,4,5,6], val 6 输出#xff1a;[1,2,3,4,5]
示例 2#xff1a; 输入#xff1a;h…目录 203. 移除链表元素
707、设计链表
206.反转链表 203. 移除链表元素
题意删除链表中等于给定值 val 的所有节点。
示例 1 输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5]
示例 2 输入head [], val 1 输出[]
示例 3 输入head [7,7,7,7], val 7 输出[] 1、感觉最好的写法还是设置虚拟结点。
2、删除中间结点的操作是 cur-next cur-next-next即改变前一结点的指向记住C/C需要释放空间。删除头结点的操作是head head-next。
3、设置好虚拟结点后就将删除结点的操作统一为了cur-next cur-next-next C版本
/*** 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* dummyHead new ListNode(0);dummyHead-next head;ListNode* cur dummyHead;while(cur-next!nullptr){if(cur-next-val val){ListNode* tmp cur-next;cur-next cur-next-next;delete tmp;}else{cur cur-next;}}head dummyHead-next;delete dummyHead;return head;}
};
Python版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def removeElements(self, head: Optional[ListNode], val: int) - Optional[ListNode]:dummyHead ListNode()dummyHead.next headcur dummyHeadwhile(cur.next!None):if cur.next.val val:cur.next cur.next.nextelse:cur cur.nextreturn dummyHead.next 707、设计链表
在链表类中实现这些功能
get(index)获取链表中第 index 个节点的值。如果索引无效则返回-1。addAtHead(val)在链表的第一个元素之前添加一个值为 val 的节点。插入后新节点将成为链表的第一个节点。addAtTail(val)将值为 val 的节点追加到链表的最后一个元素。addAtIndex(index,val)在链表中的第 index 个节点之前添加值为 val 的节点。如果 index 等于链表的长度则该节点将附加到链表的末尾。如果 index 大于链表长度则不会插入节点。如果index小于0则在头部插入节点。deleteAtIndex(index)如果索引 index 有效则删除链表中的第 index 个节点。
这个题挺简单的还是按照设置虚拟结点主要是为了方便deleteAtIndex。
另外需要注意的是题目中index的范围是从0开始的也就是说index0的结点代表head结点。所以index的范围是[0,size)注意是开区间。 while(index--){ // 如果--index 就会陷入死循环 cur cur-next; }
于是这条语句就可以实现跳转到对应结点。
C版本
class MyLinkedList {
public:// 定义链表节点结构体struct LinkedNode {int val;LinkedNode* next;LinkedNode(int val):val(val), next(nullptr){}};// 初始化链表MyLinkedList() {_dummyHead new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点而不是真正的链表头结点_size 0;}// 获取到第index个节点数值如果index是非法数值直接返回-1 注意index是从0开始的第0个节点就是头结点int get(int index) {if (index (_size - 1) || index 0) {return -1;}LinkedNode* cur _dummyHead-next;while(index--){ // 如果--index 就会陷入死循环cur cur-next;}return cur-val;}// 在链表最前面插入一个节点插入完成后新插入的节点为链表的新的头结点void addAtHead(int val) {LinkedNode* newNode new LinkedNode(val);newNode-next _dummyHead-next;_dummyHead-next newNode;_size;}// 在链表最后面添加一个节点void addAtTail(int val) {LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(cur-next ! nullptr){cur cur-next;}cur-next newNode;_size;}// 在第index个节点之前插入一个新节点例如index为0那么新插入的节点为链表的新头节点。// 如果index 等于链表的长度则说明是新插入的节点为链表的尾结点// 如果index大于链表的长度则返回空// 如果index小于0则在头部插入节点void addAtIndex(int index, int val) {if(index _size) return;if(index 0) index 0; LinkedNode* newNode new LinkedNode(val);LinkedNode* cur _dummyHead;while(index--) {cur cur-next;}newNode-next cur-next;cur-next newNode;_size;}// 删除第index个节点如果index 大于等于链表的长度直接return注意index是从0开始的void deleteAtIndex(int index) {if (index _size || index 0) {return;}LinkedNode* cur _dummyHead;while(index--) {cur cur -next;}LinkedNode* tmp cur-next;cur-next cur-next-next;delete tmp;_size--;}// 打印链表void printLinkedList() {LinkedNode* cur _dummyHead;while (cur-next ! nullptr) {cout cur-next-val ;cur cur-next;}cout endl;}
private:int _size;LinkedNode* _dummyHead;};
206.反转链表
给你单链表的头节点 head 请你反转链表并返回反转后的链表。 输入head [1,2,3,4,5]
输出[5,4,3,2,1] 解法一
把链表值保存下来再重新组织链表。缺点就是对空间复杂度要求高O(n)。
/*** 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) {vectorint nums;ListNode* cur head;while(cur ! nullptr){// coutcur-valendl;nums.push_back(cur-val);cur cur-next;}reverse(nums.begin(),nums.end());ListNode* dummyHead new ListNode(0);dummyHead-next head;ListNode* cur1 dummyHead;for(int i0; inums.size(); i){// cout nums[i] endl;cur1-next-val nums[i];cur1 cur1-next; }cur1-next nullptr;head dummyHead-next;delete dummyHead;return head;}
};
解法二、双指针法 整个逻辑就是
首先定义一个cur指针指向头结点再定义一个pre指针初始化为null。
然后就要开始反转了首先要把 cur-next 节点用tmp指针保存一下也就是保存一下这个节点。
为什么要保存一下这个节点呢因为接下来要改变 cur-next 的指向了将cur-next 指向pre 此时已经反转了第一个节点了。
接下来就是循环走如下代码逻辑了继续移动pre和cur指针。
最后cur 指针已经指向了null循环结束链表也反转完毕了。 此时我们return pre指针就可以了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) {ListNode* cur head;ListNode* pre nullptr;while(cur!nullptr){ListNode* tmp cur; // 保存当前cur指向的结点cur cur-next; // 向后移动curtmp-next pre; // 改变tmp的指向pre tmp; //向前移动pre}return pre;}
};
Python版本
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val0, nextNone):
# self.val val
# self.next next
class Solution:def reverseList(self, head: Optional[ListNode]) - Optional[ListNode]:cur headpre Nonewhile(cur ! None):tmp curcur cur.nexttmp.next prepre tmpreturn pre
