给你一个链表,删除链表的倒数第
n
个结点,并且返回链表的头结点。来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/remove-nth-node-from-end-of-list
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
示例 1:
输入:head = [1,2,3,4,5], n = 2
输出:[1,2,3,5]
示例 2:
输入:head = [1], n = 1
输出:[]
示例 3:
输入:head = [1,2], n = 1
输出:[1]
思路
- 常规的链表寻找特殊节点,两次遍历利用手动记录的index取操作链表
- 利用快慢指针寻找规律,当next为null时就可以找到该节点
/**
* 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 removeNthFromEnd1 = function (head, n) {
let count = 1,
next = head.next;
while (next) {
count++
next = next.next
}
let index = count - n + 1
let result = new ListNode(0, head);
count = 1
let tmp = result;
while (tmp) {
if (count++ == index) {
tmp.next = tmp.next.next;
} else {
tmp = tmp.next;
}
}
return result.next;
};
var removeNthFromEnd2 = function (head, n) {
let star = new ListNode(0, head),
end = new ListNode(0, head);
let result1 = star,
result2 = end;
let count = 1;
while (result2.next) {
if (count > n) {
result1 = result1.next
}
result2 = result2.next
count++
}
result1.next = result1.next.next
return star.next;
};
One comment
叼茂SEO.bfbikes.com