力扣题目链接[1]
给你一个链表,删除链表的倒数第n
个结点,并且返回链表的头结点。
示例1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
「提示:」
sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz
思路:
本题适合使用快慢指针求解。首先声明一个哨兵节点,作为链表的新头部。最终返回哨兵节点的next
指向,就是链表的头节点。
然后声明快慢指针,首先让快指针先走n
步。然后快慢指针同步走,直到快指针走到链表尾部,此时慢指针所处位置就是倒数第n + 1
个节点。因为我们声明了一个哨兵节点,所以慢指针的下一步就是倒数第n
个节点,所以删除该节点的逻辑就是将该节点的下下个next
指向,重新指向给当前节点的next
指向,就达到了删除节点的目的。
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} head
* @param {number} n
* @return {ListNode}
*/
var removeNthFromEnd = function(head, n) {
// 哨兵节点
let dump = new ListNode();
dump.next = head;
// 快慢指针
let fast = slow = dump;
// 快指针先走n步
while(n--) {
fast = fast.next;
}
// 快指针走到最后,当前slow为倒数第n+1个节点
while(fast && fast.next) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dump.next;
};
给定两个以字符串形式表示的非负整数 num1 和 num2,返回 num1 和 num2 的乘积,它们的乘积也表示为字符串形式。
注意:不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 1:
输入: num1 = "2", num2 = "3"
输出: "6"
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
提示:
1 <= num1.length, num2.length <= 200
思路:
两个数M和N相乘的结果可以由 「M 乘上 N 的每一位数的和得到。」
因此可以:
num1
依次乘上 num2
的每一位的和num1 * num2
的结果/**
* @param {string} num1
* @param {string} num2
* @return {string}
*/
let multiply = function(num1, num2) {
if(num1 === '0' || num2 === '0') return "0"
let res = []
for(let i = 0; i < num1.length; i++){
let tmp1 = +num1[num1.length - 1 - i]
for(let j = 0; j < num2.length; j++){
let tmp2 = +num2[num2.length - 1 - j]
let pos = res[i + j] ? res[i + j] + tmp1 * tmp2 : tmp1 * tmp2
res[i + j] = pos % 10
pos >=10 && (res[i + j + 1] = res[i + j + 1] ? res[i + j + 1] + Math.floor(pos / 10) : Math.floor(pos / 10));
}
}
return res.reverse().join("");
}
「复杂度分析:」
上面代码的核心逻辑是:
num1
从低位到高位的每一个数字;num2
从低位到高位的每一个数字;res
指定位上的数字;最终将res翻转并拼接成字符串返回。因为res
的保存顺序是由低位到高位,因此需要进行翻转。
[1]
力扣题目链接: https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/