给定单向链表的一个节点指针,定义一个函数在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);
}
};
输入两个递增排序的链表,合并这两个链表并使新链表中的结点仍然是按照递增排序的。
链表长度 [0,500]。
输入:1->3->5 , 2->4->5
输出:1->2->3->4->5->5
/**
* 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;
}
};
请你写一个函数 StrToInt,实现把字符串转换成整数这个功能。
当然,不能使用 atoi 或者其他类似的库函数。
这里顺便介绍一下atoi函数.
可以采用atoi函数将字符串转换为值。
atoi(str.c_str())
输入字符串长度 [0,20]。
输入:"123"
输出:123
注意:
你的函数应满足下列条件:
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;
}
};