【leetcode】力扣算法之删除链表中倒数第n个节点【中等难度】

删除链表中倒数第n个节点

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

用例

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

提示

• 链表中结点的数目为 sz
• 1 <= sz <= 30
• 0 <= Node.val <= 100
• 1 <= n <= sz

示例代码

解法1：普通解法

var removeNthFromEnd = function(head, n) {
    let len=0;
    let rootNode=head;
    while(head){
        len++;
        head=head.next;
    }
    if(len==1) return null;
    len=len-n+1;//截取的目标位置
    let i=1;
    head=rootNode;
    while(head){
        console.log(i,head.val)
        if(i==len-1){
            //删除下一个节点
            head.next=head.next.next;
            break;
        }
        if(i==len){
           //删除当前
           rootNode=head.next;
           break;
        }
        i++;
        head=head.next;
    }
    return rootNode;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

解法2：辅助栈

/**
 * 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 stack=[]
    let root=head;
    //入栈
    while(head){
        stack.push(head)
        head=head.next;
    }
    let next=null;
    for(let i=1;i<n;i++){
        next=stack.pop();
    }
    let del=stack.pop();//找到目标值
    let prev=stack.pop(); 
    if(prev){
        prev.next=next;
    }else{
        root=next;
    }
    return root;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

解法3： 双指针

/**
 * @param {ListNode} head
 * @param {number} n
 * @return {ListNode}
 */
var removeNthFromEnd = function(head, n) {
    let dummy=new ListNode(0,head);
    let slow=dummy;
    let first=head;
    for(let i=0;i<n;i++){
        first=first.next;
    }
    while(first){
        first=first.next;
        slow=slow.next;
    }
    slow.next=slow.next.next;
    return dummy.next;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

执行情况：双指针

Tip

越简单的题，使用越多的解法才能让自己对代码的理解得以增强哦