关于leetcode个人解题总结:刷题12-删除链表的倒数第-N-个结点

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

1. 双指针法

首先设置一个虚构头节点 pre, 目标是当删除的元素是第一个时，用 pre 头节点删除第一个节点操作很不便。指针 first 和 second 开始都指向虚构头节点 pre。而后将 second 向后挪动 n + 1 个节点，这样 first 和 second 就有 n + 1 个节点。first 和 second 指针每次往后挪动一个节点，这样当 second 指向链表尾部 null 时，first 指针此时的地位为倒数第 n + 1 个节点，因而 first.next = first.next.next 就删除了倒数第 n 个节点，最初返回 pre.next 即可。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(n <= 0) return null;
        ListNode pre = new ListNode(-1,head);
        ListNode first = pre,second = pre;

        for(int i = 0;i <= n;i++){if(second == null) return null;
            second = second.next;
        }

        while(second != null){
            first = first.next;
            second = second.next;
        }

        first.next = first.next.next;

        return pre.next;
    }

2. 栈

设置一个虚构头节点 pre, 目标是当删除的元素是第一个时，用 pre 头节点删除第一个节点操作很不便. 将所有节点从头到尾全副压进栈中，包含虚构头节点。而后从栈中弹出 n 个节点，弹出 n 个节点后栈顶的元素就是 n 的前一个节点，假如为 preNode，将 preNode.next = preNode.next.next，最初返回 pre.next 即可。

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {if(n <= 0) return null;
        ListNode pre = new ListNode(-1,head),temp = pre;
        Stack<ListNode> st = new Stack<>();
        
        while(temp != null){st.push(temp);
            temp = temp.next;
        }

        for(int i = 0;i < n && st.isEmpty() != true;i++){st.pop();
        }

        if(st.isEmpty()) return null;
        ListNode preNode = st.peek();
        preNode.next = preNode.next.next;
        return pre.next;
    }
    
}