public ListNode removeNthFromEnd(ListNode head, int n){ int length = 0; ListNode l = head; while (l != null) { length++; l = l.next; } if (length == 1) { returnnull; }
l = head;
int sub = length - n; if (sub == 0) { return head.next; } while (sub > 1) { l = l.next; sub--; } l.next = l.next.next; return head; }
虽然遍历了两次，但是时间复杂度还是 O(n)，线性长度
空间复杂度为 O(1)
思路二：相对位移法
这个思路也很简单，对比上面的思路好处是：只需要遍历一遍就行了
双指针，让 A 指针先走 n步，随后再让 B 指针和 A 指针一起走，这样就会有长度为 n 的相对位移，直到让 A 指针走到终点，此时 B 指针也就距终点 n 的长度了
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13
public ListNode removeNthFromEnd(ListNode head, int n){ ListNode fast = head, slow = head; for (int i=0; i<n; i++){ fast = fast.next; } if (fast == null) return head.next; while (fast.next != null){ fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return head; }