东莞桂城网站建设北京网站建设专业公司
题目：LCR 021
解法一：计算链表长度
遍历两次，第一次获取链表长度 L（包括虚拟节点），第二次遍历到第 L-n 个节点（从虚拟节点遍历）
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);int L = 0;ListNode temp = dummy;while (temp != null) {L++;temp = temp.next;}temp = dummy;for (int i = 1; i < L - n; i++) {temp = temp.next;}temp.next = temp.next.next;return dummy.next;}
注意：
- 建议在头节点前添加虚拟节点，因为假如要删除的是第一个元素，就不能用前节点指向后节点的方法来删除节点，因此推荐给头节点加上前驱节点
while循环条件为temp != null，而非temp.next != null
解法二：马拉车算法
将链表所以节点压入栈中，顺序弹出，弹出n个后，栈顶元素即为删除节点的前驱节点
public ListNode removeNthFromEnd(ListNode head, int n) {Stack<ListNode> stack = new Stack<>();ListNode dummy = new ListNode(0, head);ListNode temp = dummy;while (temp != null) {stack.push(temp);temp = temp.next;}for (int i = 0; i < n; i++) {stack.pop();}temp = stack.peek();temp.next = temp.next.next;return dummy.next;}
注意：while 循环条件为 temp != null，而非 temp.next != null
解法三：双指针
设置双指针，前指针指向第 n 个节点，后指针指向头节点，同时向后遍历，当前指针遍历到尾部时，后指针指向的即为删除节点的前驱节点
public ListNode removeNthFromEnd(ListNode head, int n) {ListNode dummy = new ListNode(0, head);ListNode first = dummy;ListNode second = dummy;for (int i = 0; i < n; i++) {first = first.next;}while (first.next != null) {first = first.next;second = second.next;}second.next = second.next.next;return dummy.next;}
注意：while 循环条件为 temp.next != null，而非 temp != null