关于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;    }    }