Heading

19.删除链表的倒数第 N 个节点 (opens new window)

Tags: algorithms linked-list two-pointers

Langs: c cpp csharp golang java javascript kotlin php python python3 ruby rust scala swift typescript

• algorithms
• Medium (39.59%)
• Likes: 1101
• Dislikes: -
• Total Accepted: 279.1K
• Total Submissions: 689.5K
• Testcase Example: '[1,2,3,4,5]\n2'

给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.

/*
 * @lc app=leetcode.cn id=19 lang=javascript
 *
 * [19] 删除链表的倒数第 N 个结点
 * 暴利解法
 */

// @lc code=start
/**
 * 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 length = 0
    let p = head
    while (p) {
        p = p.next
        length++
    }

    const targetIndex = length - n
    if (targetIndex < 0) {
        return head
    } else if (targetIndex === 0) {
        return head.next
    } else {
        p = head
        let q
        let iterCount = 0
        while (p) {
            if (iterCount === targetIndex) {
                q.next = p.next
                return head
            }
            q = p
            p = p.next
            iterCount++
        }
    }
}
// @lc code=end

/*
 * @lc app=leetcode.cn id=19 lang=javascript
 *
 * [19] 删除链表的倒数第N个节点
 * 双指针
 */

// @lc code=start
/**
 * 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) {
    const dummy = new ListNode(0, head);
    let first = head,
        second = dummy;
    while (first && n-- > 0) {
        first = first.next
    }
    while (first) {
        first = first.next
        second = second.next
    }
    second && (second.next = second.next.next)
    return dummy.next
};
// @lc code=end
// @after-stub-for-debug-begin
module.exports = removeNthFromEnd;
// @after-stub-for-debug-end