文章目录
- 题目
- 方法一：节点加入集合找索引
- 方法二：直接计算长度,然后找出要删除的节点的前一个节点
- 方法三：栈
- 方法四：前后双指针
题目
这题的关键在与两个点
-
一定要设置一个哑结点，防止删除第一个元素时，导致空指针异常
-
删除链表的元素其实就等价于找到这个元素的前一个元素
方法一：节点加入集合找索引
先将ListNode存到list 然后直接找到要删除节点的前一个节点即可（node.next = node.next.next）
public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode pre = new ListNode(0, head);//创建哑结点 解决要删除的元素时第一个 空指针异常List<ListNode> list = new ArrayList<>();//将链表节点存到listListNode h = pre;while(h != null){list.add(h);h = h.next;}//找到要删除的数的前一个节点ListNode node = list.get(list.size()-1-(n-1)-1);node.next = node.next.next;return pre.next;}
方法二：直接计算长度,然后找出要删除的节点的前一个节点
public static ListNode removeNthFromEnd(ListNode head, int n) {//得出链表的长度int length = getLength(head);ListNode pre = new ListNode(0, head);//创建哑结点 解决要删除的元素时第一个 空指针异常//倒数n个 为 length - n + 1int l = length - n + 1;ListNode cur = pre;for (int i = 1; i < l ; i++ ) {cur = cur.next;}cur.next = cur.next.next;return pre.next;}//计算链表长度public static int getLength(ListNode head){int len = 0;while(head !=null){len ++;head = head.next;}return len;}
方法三：栈
依次入栈，直到null 然后要删除的元素 n = 多少 就弹出对少元素 弹出的元素就是要删除的元素 例如找n=1 倒数第一个 则直接弹出栈顶元素删除即可
此时当弹出n个数之后 ，此时栈顶其实就是要删除的数的前一个数了，也满足将删除链表元素转换为找到要删除元素的前一个元素
public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//哑结点 删除第一个元素空指针异常Deque<ListNode> stack = new LinkedList<ListNode>(); //栈ListNode cur = dummy;while (cur != null) {stack.push(cur);cur = cur.next;}for(int i = 0; i<n ; i++){stack.pop();//弹出对应的栈顶元素 最后弹出的元素就是要删除的元素}//此时要删除的前一个元素时栈顶元素ListNode pre = stack.peek();pre.next = pre.next.next;return dummy.next;}
方法四：前后双指针
关键在于指针的设置，fast起始就比slow快一个节点，然后按照n=？ fast往前移动？个位置，然后再slow和fast同步移动，直到fast走到null，此时slow指向的就是要删除元素的前一个位置（也就是为什么开始就要fast比slow快一个位置的原因，不然等fast走到null了，结果slow指向的要删除的元素，这样不太好执行node.next = node.next.next操作，因为删除链表的元素其实就等价于找到这个元素的前一个元素）
public static ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);//哑结点 防止删除第一个元素空指针异常ListNode fir = head;ListNode bef = dummy;//先指针领先 bef n 个位置for(int i=0;i<n;i++){fir = fir.next;}//当 fir遍历到链表的末尾时， bef的下一个节点就是我们需要删除的节点。while(fir !=null){fir =fir.next;bef = bef.next;}bef.next = bef.next.next;return dummy.next;}
