image.png

解法1

先遍历一遍计算链表长度，再遍历一遍删除倒数第n个节点
时间复杂度O(n)
但是遍历了两遍链表

解法2

只遍历一遍链表
同样地加上一个虚拟头结点
image.png
对应这个链表，要删除的是p,需要找到p前面的一个节点
image.png
这时p指向要删除节点的前一个节点，q指向尾节点
然后，将p,q向前挪，使p指向虚拟头结点
由于p到q之间的长度是固定的，所以如果p是虚拟头结点的话，那么q应该是p向后移动n+1次
image.png
接下来让p和q同时向前移动，此时p和q之间的距离并不会发生变化
image.png
一直到q指向了null,那么p就指向了要删除元素的前一个节点
image.png
这样，只遍历了一遍链表，使用两个指针进行辅助

code

  1. public ListNode removeNthFromEnd(ListNode head, int n) {
  2.         //虚拟头结点
  3.         ListNode dummyHead = new ListNode(0);
  4.         dummyHead.next = head;
  5.         //声明快慢指针
  6.         ListNode slow = dummyHead;
  7.         ListNode fast = dummyHead;
  8.         //快指针先走n+1步
  9.         for(int i=0;i<n+1;i++)
  10.             fast = fast.next;
  11.         //同时向后移动，直到快指针为null,此时慢指针指向待删除元素的前一个节点
  12.         while(fast!=null){
  13.             slow = slow.next;
  14.             fast = fast.next;
  15.         }
  16.         //删除节点
  17.         slow.next = slow.next.next;
  18.         //返回真实头结点
  19.         return dummyHead.next;
  20.     }
  21. // time O(n)
  22. // space O(1)