LeetCode 19：删除链表的倒数第 N 个结点

小半 • 2023年2月3日上午10:49 • 技术随笔 • 阅读 229

题目：

方法一：快慢指针

如果要删除倒数第n个节点，让fast移动n步，目的是拉开fast和slow之间的距离；
然后让fast和slow同时移动，直到fast指向链表末尾，此时slow就是要删除的节点！
最后fast为末尾节点的next即为null，slow就是要删除的节点node，而pre节点记录了node的前节点！


class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(n<=0){
            return head;
        }
        // 哨兵节点！
        ListNode mer=new ListNode(-1);
        mer.next=head;
        
        ListNode fast=mer;
        ListNode slow=mer;
        //fast移动n次
        for(int i=0;i<n;i++){
            fast=fast.next;
        }
        ListNode pre=null;
        while(fast!=null){
            pre=slow;
            // slow和fast一起移动，直到fast到末尾
            slow=slow.next;
            fast=fast.next;
        }
        // 删除
        pre.next=slow.next;
        return mer.next;

    }
}

方法二：模拟

直接按情况分类计算；
排除k>size和k=size=1的特殊情况；
如果k=1且size>1，即删除最后一个节点；
如果k>1且k=size，即删除第一个，那么直接返回第二个节点即可；
而k>1且k<size时，将前驱节点指向要删除节点的next即完成删除；


class Solution {
    public ListNode removeNthFromEnd(ListNode head, int k) {
        Stack<ListNode> s=new Stack<>();
        ListNode curr=head;
        while(curr!=null){
            s.push(curr);
            curr=curr.next;
        }
        // base case
        if(k>s.size() || k<=0){
            return head;
        }
        if(k==1 && s.size()==1){
            return null;
        }

		else if(k==1 && s.size()>1 ){
            s.pop();
            ListNode pre=s.pop();
            pre.next=null;

        }else if(k>1 && k==s.size()){
            ListNode second=null;
            for(int i=0;i<k-1;i++){
                second=s.pop();
            }
            return second;
        }else if(k>1 && k<s.size()){
            ListNode front=null;
            for(int i=0;i<k+1;i++){
                front=s.pop(); // 前
            }
            front.next=front.next.next;
        }

        return head;


    }
}