赞
踩
给你一个链表的头节点
head
和一个整数val
,请你删除链表中所有满足Node.val == val
的节点,并返回 新的头节点 。示例 1:
输入:head = [1,2,6,3,4,5,6], val = 6 输出:[1,2,3,4,5]
- // 时间复杂度:O(n)
- // 空间复杂度:O(1)
- // 直接在原来的链表执行删除
- /**
- * 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) {
- // 判断是否需要删除头节点
- // 头节点的删除不能靠将前一个节点的next指向其后一个节点
- // 只需要将头指针指向第二个节点即可
- while (head != nullptr && head->val == val) { // 链表非空且头节点符合条件
- // 注意,由于最前边可能连续有好几个节点值和待移除值相同,所以要用while,不能用if
- // 使用temp节点保存头节点,后续要delete
- ListNode* temp = head;
- head = head->next;
- delete temp;
- }
-
- // 删除非头节点
- ListNode* cur = head; // 遍历所用的指针
- while (cur != nullptr && cur->next != nullptr) { // 链表非空且当前节点不是尾节点
- if (cur->next->val == val) {
- // 前边的代码已经确保头指针不用删除, 直接看下一个节点
- // 链表移除节点需要节点前一个和后一个节点参与,但单链表当前节点无法访问前一个节
- // 所以在移除时,关注的是当前节点的后两个节点
- ListNode* temp = cur->next;
- cur->next = cur->next->next;
- delete temp;
- } else {
- cur = cur->next;
- }
- }
- return head;
- }
- };

- // 时间复杂度:O(n)
- // 空间复杂度:O(1)
- // 添加虚拟头节点再执行删除
- /**
- * 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(0);
- dummy_head->next = head; // 将虚拟头结点指向head,这样头节点也有方便后面做删除操作
-
- ListNode* cur = dummy_head; // 遍历所用的指针
- while (cur->next != nullptr) { // 当前节点不是尾节点,添加了虚拟头节点,链表肯定非空,不用再加cur != nullptr
- if (cur->next->val == val) {
- ListNode* temp = cur->next;
- cur->next = cur->next->next;
- delete temp;
- } else {
- cur = cur->next; // 更新遍历指针
- }
- }
- head = dummy_head->next; // 更新头指针,因为原来的头节点可能已被删除了
- delete dummy_head; // 释放虚拟头节点
- return head;
- }
- };

你可以选择使用单链表或者双链表,设计并实现自己的链表。
单链表中的节点应该具备两个属性:
val
和next
。val
是当前节点的值,next
是指向下一个节点的指针/引用。如果是双向链表,则还需要属性
prev
以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。实现
MyLinkedList
类:
MyLinkedList()
初始化MyLinkedList
对象。int get(int index)
获取链表中下标为index
的节点的值。如果下标无效,则返回-1
。void addAtHead(int val)
将一个值为val
的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。void addAtTail(int val)
将一个值为val
的节点追加到链表中作为链表的最后一个元素。void addAtIndex(int index, int val)
将一个值为val
的节点插入到链表中下标为index
的节点之前。如果index
等于链表的长度,那么该节点会被追加到链表的末尾。如果index
比长度更大,该节点将 不会插入 到链表中。void deleteAtIndex(int index)
如果下标有效,则删除链表中下标为index
的节点。示例:
输入 ["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"] [[], [1], [3], [1, 2], [1], [1], [1]] 输出 [null, null, null, null, 2, null, 3] 解释 MyLinkedList myLinkedList = new MyLinkedList(); myLinkedList.addAtHead(1); myLinkedList.addAtTail(3); myLinkedList.addAtIndex(1, 2); // 链表变为 1->2->3 myLinkedList.get(1); // 返回 2 myLinkedList.deleteAtIndex(1); // 现在,链表变为 1->3 myLinkedList.get(1); // 返回 3
- class MyLinkedList {
- public:
- // 定义单链表节点结构体
- struct LinkedNode {
- int val;
- LinkedNode* next;
- // 注意建立了有参构造,默认的无参构造就不提供了
- LinkedNode(int val):val(val), next(nullptr) {}
- };
-
- // 初始化链表
- MyLinkedList() {
- _dummy_head = new LinkedNode(0);
- _size = 0; // 虚拟头节点不算在链表长度
- }
-
- // 获取第index个节点的数值,如果index非法,返回-1
- // 注意index从0开始,0指的是头节点
- int get(int index) {
- if (index < 0 || index > (_size - 1)) {
- return -1;
- }
- LinkedNode* cur = _dummy_head->next; // 从头节点开始遍历
- while (index--) { // 0索引直接跳出循环
- cur = cur->next;
- }
- return cur->val;
- }
-
- // 在链表最前面插入一个节点,作为新的头节点
- void addAtHead(int val) {
- LinkedNode* newNode = new LinkedNode(val);
- newNode->next = _dummy_head->next;
- _dummy_head->next = newNode;
- _size++; // 注意不要忘了更新size
- }
-
- // 在链表最后面添加一个节点
- void addAtTail(int val) {
- LinkedNode* newNode = new LinkedNode(val);
- LinkedNode* cur = _dummy_head;
- while (cur->next != nullptr) { // cur到尾节点推出
- 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 = _dummy_head; // 在前边插入,这里不要-1
- while (index--) { // index=0时直接跳出,cur->next是插入的位置
- cur = cur->next;
- }
- newNode->next = cur->next;
- cur->next = newNode;
- _size++;
- }
-
- void deleteAtIndex(int index) {
- if (index < 0 || index > (_size - 1)) return;
- LinkedNode* cur = _dummy_head;
- while(index--) {
- cur = cur->next;
- }
- LinkedNode* temp = cur->next;
- cur->next = cur->next->next;
- delete temp;
- //delete命令指示释放了tmp指针原本所指的那部分内存,
- //被delete后的指针tmp的值(地址)并非就是NULL,而是随机值。也就是被delete后,
- //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
- //如果之后的程序不小心使用了tmp,会指向难以预想的内存空间
- temp = nullptr;
- _size--;
- }
-
- // 打印链表
- void printLinkedList() {
- LinkedNode* cur = _dummy_head;
- while(cur->next != nullptr) {
- cout << cur->next->val << " ";
- cur = cur->next;
- }
- cout << endl;
- }
-
- private:
- int _size;
- LinkedNode* _dummy_head;
- };
-
- /**
- * 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);
- */

直观来说,重新创建一个空链表,然后再将原链表的每个节点依次插入到新建链表的头节点,时间和空间复杂度都是O(n)
cur指针负责遍历链表,将遍历到的节点的next赋值为前一个节点,也就是pre指针指向的节点。由于cur的next的指向已经被修改了,遍历无法继续,于是还需要一个temp指针,提前保存cur->next的值(纠正:动画应该是先移动pre,在移动cur)
- // 时间复杂度O(n)
- // 空间复杂度O(1)
- /**
- * 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* temp; // 保存cur->next, 使循环得以继续
- ListNode* cur = head; // 控制遍历的指针
- ListNode* pre = nullptr; // cur的前一个节点,初始值为nullptr
- while (cur) { // 注意,cur==nullptr时才跳出,不是到尾节点就跳出
- temp = cur->next; // 由于cur->next被改写,破坏循环,要提前记录
- cur->next = pre; // cur->next被改为指向前一个节点
- // 更新pre和cur指针
- pre = cur; // pre前移一个节点
- cur = temp; // cur前移一个节点
- }
- return pre;
- }
- };

从前向后翻转
- // 递归法,从前向后翻转
- // 时间复杂度:O(n)
- // 空间复杂度: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* reverse(ListNode* pre, ListNode* cur) {
- if (cur == nullptr) return pre;
- ListNode* temp = cur->next;
- cur->next = pre;
- // 可以和双指针法的代码进行对比,如下递归的写法,其实就是做了这两步
- // pre = cur;
- // cur = temp;
- return reverse(cur, temp);
- }
-
- ListNode* reverseList(ListNode* head) {
- // 和双指针法初始化是一样的逻辑
- // ListNode* cur = head;
- // ListNode* pre = nullptr;
- return reverse(nullptr, head);
- }
- };

还有另外一种与双指针法不同思路的递归写法:从后往前翻转指针指向
- class Solution {
- public:
- ListNode* reverseList(ListNode* head) {
- // 边缘条件判断
- if(head == nullptr) return nullptr; // 空链表返回空链表
- if (head->next == nullptr) return head; // 仅有一个节点返回原链表
-
- // 超过一个节点,递归调用
- // 递归到尾节点,开始返回,返回的是尾节点指针
- ListNode *last = reverseList(head->next); // 递归函数有返回值,这个返回值不修改返回,那么最后递归完成后的返回值,也就是初次返回的返回值
- // 从后向前,倒数第二次递归传入的是倒数第二个节点指针
- // 翻转倒数第二个节点和倒数第一个节点
- // 随着递归的依次返回,接下来传入倒数第三个、第四个,直到头节点
- // 翻转头节点与第二个节点的指向
- head->next->next = head;
- // 此时的 head 节点为尾节点,next 需要指向 NULL
- head->next = nullptr;
- return last; // 将尾节点,也就是反转后的头节点指针返回
- }
- };

Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。