代码随想录（Day 3）

已于 2024-04-07 19:24:49 修改
阅读量1.9k 收藏 47
点赞数 28
文章标签： leetcode
于 2024-04-07 18:38:13 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/vKohl/article/details/137438280
版权

今日任务
1.移除链表元素
2.设计链表
3.翻转链表
4.两两交换链表中的结点

1.移除链表元素

LeetCode链接

链表经典操作，对于原理不过多解释，主要探讨建立虚拟头结点和不建立虚拟头结点的区别。

对于链表操作时，大多数参考书上都给出头结点不需要带数据，这样做是有道理的。
因为在链表中，我们涉及到链表的操作时，除了改变结点指针指向就是删除与增加结点了。

而我们在删除结点时，对于链表中部结点，几乎都能联想到3个结点之间的操作，无非就是第1个结点通过指针指向第3个结点，再free掉第二个结点。
而到链表首结点时，只有首结点和次结点了，有时候容易忘记操作，无非就是再引入一个虚拟头结点，并将head对其赋值，然后free掉虚拟头结点再使head往后移就行了。

所以，我们为什么不直接在一开始就引入一个头结点呢，使得头结点后面next真正的头结点，最后return dummynode->next；就行了，给出代码

这是不带头结点

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

这是带头结点

class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head; 
        ListNode* cur = dummyHead;
        while (cur->next != NULL) {
            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;
    }
};

2.设计链表

LeetCode链接

题意

  • get(index)：获取链表中第 index 个节点的值。如果索引无效，则返回-1。
  • addAtHead(val)：在链表的第一个元素之前添加一个值为 val 的节点。插入后，新节点将成为链表的第一个节点。
  • addAtTail(val)：将值为 val 的节点追加到链表的最后一个元素。
  • addAtIndex(index,val)：在链表中的第 index 个节点之前添加值为 val  的节点。如果 index 等于链表的长度，则该节点将附加到链表的末尾。如果 index 大于链表长度，则不会插入节点。如果index小于0，则在头部插入节点。
  • deleteAtIndex(index)：如果索引 index 有效，则删除链表中的第 index 个节点。

此题目我们主要来探讨主函数模式和主输入模式之间的相互转换

我个人在做题中发现，用惯了LeetCode的主函数模式刷题，而在面对ACM中的主输入模式后会很难下手。

首先我先贴出主输入模式的代码（较长）

先给出题目

输入数据只有一组，第一行有n+1个整数，第一个整数是这行余下的整数数目n，后面是n个整数。
这一行整数是用来初始化列表的，并且输入的顺序与列表中的顺序相反，也就是说如果列表中是1、2、3那么输入的顺序是3、2、1。（初始化链表的元素是倒序的，这个使用题目中创建列表的方法（从头部插入）就可以了。）
第二行有一个整数m，代表下面还有m行。每行有一个字符串，字符串是“get”，“insert”，“delete”，“show”中的一种。
如果是“get”，代表获得第a个元素。（a从1开始计数）
如果是“delete”，代表删除第a个元素。（a从1开始计数）
如果是“insert”，则其后跟着两个整数a和e，代表在第a个位置前面插入e。（a从1开始计数）
“show”之后没有正数，直接打印链表全部内容。

#include<iostream>
using namespace std;
// 定义链表节点结构体
struct LinkedNode {
    int val;
    LinkedNode* next;
    LinkedNode(int val):val(val), next(nullptr){}
};

int _size = 0;
LinkedNode* _dummyHead =  new LinkedNode(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，则在头部插入节点
int addAtIndex(int index, int val) {

    if(index > _size) return -1;
    if(index < 0) return -1;
    LinkedNode* newNode = new LinkedNode(val);
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur->next;
    }
    newNode->next = cur->next;
    cur->next = newNode;
    _size++;
    return 0;
}

// 删除第index个节点，如果index 大于等于链表的长度，直接return，注意index是从0开始的
int deleteAtIndex(int index) {
    if (index >= _size || index < 0) {
        return -1;
    }
    LinkedNode* cur = _dummyHead;
    while(index--) {
        cur = cur ->next;
    }
    LinkedNode* tmp = cur->next;
    cur->next = cur->next->next;
    delete tmp;
    //delete命令指示释放了tmp指针原本所指的那部分内存，
    //被delete后的指针tmp的值（地址）并非就是NULL，而是随机值。也就是被delete后，
    //如果不再加上一句tmp=nullptr,tmp会成为乱指的野指针
    //如果之后的程序不小心使用了tmp，会指向难以预想的内存空间
    tmp=nullptr;
    _size--;
    return 0;
}

// 打印链表
int printLinkedList() {
    LinkedNode* cur = _dummyHead;
    if (cur->next == nullptr) return -1;
    while (cur->next != nullptr) {
        cout << cur->next->val << " ";
        cur = cur->next;
    }
    cout << endl;
    return 0;
}

int main() {
    int n, a, m, t, z;
    string s;
    cin >> n;
    LinkedNode* head = nullptr;
    while (n--) {
        cin >> a;
        addAtHead(a);
    }
    cin >> m;
    while (m--) {
        cin >> s;
        if (s == "show")  {
            if (printLinkedList() == -1) cout << "Link list is empty" << endl;
        }
        if (s == "delete") {
            cin >> t; 
            // 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
            if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl; 
            else cout << "delete OK" << endl;
        }
        if (s == "insert") {
            cin >> t >> z; 
            if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
            else cout << "insert OK" << endl;

        }
        if (s == "get") {
            cin >> t;
            int getValue = get(t - 1);
            if (getValue == -1) cout << "get fail" << endl;
            else cout << getValue << endl;
        }
    }
}

再给出主函数的代码

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++;
    }

在这里我想把这两个代码之间的区别直接贴出来，不然太长串不好看

第一个区别，在主输入模式中， 变量是直接定义在全局下的

int _size = 0;
LinkedNode* _dummyHead =  new LinkedNode(0); // 这里定义的头结点 是一个虚拟头结点，而不是真正的链表头结点

而主函数模式下，变量是定义在private成员里面

private:
    int _size;
    LinkedNode* _dummyHead;

最重要的便是主输入模式下的主函数了

int main() {
    int n, a, m, t, z;
    string s;
    cin >> n;
    LinkedNode* head = nullptr;
    while (n--) {
        cin >> a;
        addAtHead(a);
    }
    cin >> m;
    while (m--) {
        cin >> s;
        if (s == "show")  {
            if (printLinkedList() == -1) cout << "Link list is empty" << endl;
        }
        if (s == "delete") {
            cin >> t; 
            // 本题的删除索引是从1开始，函数实现是从0开始，所以这里是 t - 1
            if (deleteAtIndex(t - 1) == -1) cout << "delete fail" << endl; 
            else cout << "delete OK" << endl;
        }
        if (s == "insert") {
            cin >> t >> z; 
            if (addAtIndex(t - 1, z) == -1) cout << "insert fail" << endl;
            else cout << "insert OK" << endl;

        }
        if (s == "get") {
            cin >> t;
            int getValue = get(t - 1);
            if (getValue == -1) cout << "get fail" << endl;
            else cout << getValue << endl;
        }
    }
}
  1. 首先，读取用户输入的整数 n，表示要插入到链表中的节点个数。
  2. 使用一个循环，读取 n 个整数 a，并调用 addAtHead(a) 将这些节点插入到链表的头部。
  3. 读取用户输入的整数 m，表示接下来要执行的命令个数。
  4. 使用一个循环，读取用户输入的命令 s，并根据命令执行相应的操作。
    • 如果命令是 "show"，调用 printLinkedList() 打印链表中的元素。
    • 如果命令是 "delete"，读取要删除的节点索引 t，调用 deleteAtIndex(t - 1) 删除对应索引的节点。
    • 如果命令是 "insert"，读取要插入的节点索引 t 和值 z，调用 addAtIndex(t - 1, z) 在对应索引之前插入新节点。
    • 如果命令是 "get"，读取要获取的节点索引 t，调用 get(t - 1) 获取对应索引的节点值。
  5. 执行完所有命令后，程序结束。

3.翻转链表（小重点） 

LeetCode链接

先给出图解

由这两张图我们就能很清晰的分析出了

1.首先先建立一个pre指针指向null
2.再为head头指针建立一个别名cur
3.别忘记用temp来临时保存一下cur的next位置

给出代码

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* temp; // 保存cur的下一个节点
        ListNode* cur = head;
        ListNode* pre = NULL;
        while(cur) {
            temp = cur->next;  // 保存一下 cur的下一个节点，因为接下来要改变cur->next
            cur->next = pre; // 翻转操作
            // 更新pre 和 cur指针
            pre = cur;
            cur = temp;
        }
        return pre;
    }
};

4.两两交换链表中的结点 

LeetCode链接

此类题目的话尽量从图去理解，说再多不如给几张图即可

  

 对应的C++代码实现如下：

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode* dummyHead = new ListNode(0); // 设置一个虚拟头结点
        dummyHead->next = head; // 将虚拟头结点指向head，这样方便后面做删除操作
        ListNode* cur = dummyHead;
        while(cur->next != nullptr && cur->next->next != nullptr) {
            ListNode* tmp = cur->next; // 记录临时节点
            ListNode* tmp1 = cur->next->next->next; // 记录临时节点

            cur->next = cur->next->next;    // 步骤一
            cur->next->next = tmp;          // 步骤二
            cur->next->next->next = tmp1;   // 步骤三

            cur = cur->next->next; // cur移动两位，准备下一轮交换
        }
        return dummyHead->next;
    }
};

vKohl
关注
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值