河南省人民政府驻上海办事处_珠海企业官网设计制作_鞍山seo外包_关键词seo优化软件

题目介绍

解法

法一：前后指针

思路：让前面的指针先移动 n 步，之后前后指针共同移动（左右指针的距离始终为n），直到前面的指针到尾部，此时前指针移动到了要删除节点的前一个节点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {// 由于可能会删除链表头部，用哨兵节点简化代码ListNode dummy = new ListNode(0, head);ListNode left = dummy, right = dummy;while (n-- > 0) {right = right.next; // 右指针先向右走 n 步}while (right.next != null) {left = left.next;right = right.next; // 左右指针一起走}left.next = left.next.next; // 左指针的下一个节点就是倒数第 n 个节点return dummy.next;}
}

法二：暴力方法

先遍历整个链表得到链表长度l，再从头开始移动指针l-n-1次，移动到要删除节点的前一个节点

class Solution {public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int length = getLength(head);ListNode cur = dummy;for (int i = 1; i < length - n + 1; ++i) {cur = cur.next;}cur.next = cur.next.next;ListNode ans = dummy.next;return ans;}public int getLength(ListNode head) {int length = 0;while (head != null) {++length;head = head.next;}return length;}
}