[数据结构与算法]每日算法刷题Day13-在O(1)时间删除链表结点、合并两个排序的链表、把字符串转换成整数

?每日算法题解系列文章旨在精选重点与易错的算法题，总结常见的算法思路与可能出现的错误，与笔者另一系列文章有所区别，并不是以知识点的形式提升算法能力，而是以实战习题的形式理解算法，使用算法。

🔥本文已收录于算法刷题系列专栏： 每日算法题解 欢迎订阅，持续更新。

39.在O(1)时间删除链表结点

给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。

假设链表一定存在，并且该节点一定不是尾节点。

数据范围

链表长度 [1,500]。

样例

输入：链表 1->4->6->8
      删掉节点：第2个节点即6（头节点为第0个节点）

输出：新链表 1->4->8

思路

由于给出的模板只传入了当前节点，前一个节点的next必指向该节点，无法找到前一个节点的地址，因此无法修改指向关系，这里只能采用“伪装”的思想，只需要将当前节点伪装成下一个节点即可。其value等于下一个节点的value，指针也指向下下个节点。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        node -> val = node -> next ->val;
        node -> next = node -> next ->next;
    }
};

由于是完全替代下一个节点，我们也可以采用简化的写法如下

class Solution {
public:
    void deleteNode(ListNode* node) {
        *(node) = *(node -> next);
    }
};

40.合并两个排序的链表

输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。

数据范围

链表长度 [0,500]。

样例

输入：1->3->5 , 2->4->5

输出：1->2->3->4->5->5

思路

• 首先定义一个虚拟节点作为尾节点
• 循环两个列表
  • 如果l1节点值小于l2节点，则将尾节点指向l1，这时利用从右向左的赋值顺序，在将该节点更新为尾节点。
  • l1也向后更新一位节点
  • 最后判断哪个链表还不为空，直接接在后面即可
• 返回dummy节点的指向（即合并后链表的头节点）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge(ListNode* l1, ListNode* l2) {
        auto dummy = new ListNode(-1),tail = dummy;
        while(l1 && l2)
            if(l1 -> val < l2 -> val)
            {
                tail = tail -> next = l1;
                l1 = l1 -> next;
            }
            else
            {
                tail = tail -> next = l2;
                l2 = l2 -> next;
            }
        if(l1)tail -> next = l1;
        if(l2)tail -> next = l2;
        
        return dummy ->next;
    }
};

41.把字符串转换成整数

请你写一个函数 StrToInt，实现把字符串转换成整数这个功能。

当然，不能使用 atoi 或者其他类似的库函数。

atoi

这里顺便介绍一下atoi函数.

可以采用atoi函数将字符串转换为值。

atoi(str.c_str())

数据范围

输入字符串长度 [0,20]。

样例

输入："123"

输出：123

注意:

你的函数应满足下列条件：

1. 忽略所有行首空格，找到第一个非空格字符，可以是 ‘+/?’ 表示是正数或者负数，紧随其后找到最长的一串连续数字，将其解析成一个整数；
2. 整数后可能有任意非数字字符，请将其忽略；
3. 如果整数长度为 00，则返回 00；
4. 如果整数大于 INT_MAX(231?1231?1)，请返回 INT_MAX；如果整数小于INT_MIN(?231?231) ，请返回 INT_MIN；

思路

class Solution {
public:
    int strToInt(string str) {
        int k = 0;
        long long f = 1;
        //处理正负
        while (k < str.size() && str[k] == ' ')k++;
        
        if(k < str.size() && str[k] == '-')
        {
            k++;
            f = -1;
        }
        if( k < str.size() && str[k] == '+')k++;
        
        
        long long r = 0;
        while(k < str.size() && str[k] <= '9' && str[k] >= '0')
        {
            //如果是负数，则每一位转换为负数最后相加即可
            //通过乘以10移位
            r = r*10 + f * (str[k] - '0');
            if (r < INT_MIN) return INT_MIN;
            if (r > INT_MAX) return INT_MAX;
            k ++;
        }
        return (int)r;
    }
};