19. Remove Nth Node from End of List --- Two Pointers / Linked List 经典

https://leetcode.com/problems/remove-nth-node-from-end-of-list/

博客答案：

http://www.cnblogs.com/springfor/p/3862219.html

public class Solution {

public ListNode removeNthFromEnd(ListNode head, int n) {

if (head == null || head.next == null)

return null;

ListNode faster = head;

ListNode slower = head;

for (int i = 0; i < n; i++) {

faster = faster.next;

}

if (faster == null) {

head = head.next;

return head;

}

while (faster.next != null) {

faster = faster.next;

slower = slower.next;

}

slower.next = slower.next.next;

return head;

}

}

首先先让faster从起始点往后跑n步。

然后再让slower和faster一起跑，直到faster==null时候，slower所指向的node就是需要删除的节点。

注意，一般链表删除节点时候，需要维护一个prev指针，指向需要删除节点的上一个节点。

为了方便起见，当让slower和faster同时一起跑时，就不让 faster跑到null了，让他停在上一步，faster.next==null时候，这样slower就正好指向要删除节点的上一个节点，充当了prev指针。这样一来，就很容易做删除操作了。

slower.next = slower.next.next(类似于prev.next = prev.next.next)。

同时，这里还要注意对删除头结点的单独处理，要删除头结点时，没办法帮他维护prev节点，所以当发现要删除的是头结点时，直接让head = head.next并returnhead就够了。

259. 3Sum Smaller -- 【M】

https://leetcode.com/problems/3sum-smaller/

https://segmentfault.com/a/1190000003794736

public class Solution {

public int threeSumSmaller(int[] nums, int target) {

if (nums.length < 3)

return 0;

int count = 0;

Arrays.sort(nums);

for (int i = 0; i < nums.length - 2; i++) {

int left = i + 1;

int right = nums.length - 1;

while (left < right) {

int sum = nums[i] + nums[left] + nums[right];

if (sum >= target) {

right--;

}

else {

count = count + right - left;

left++;

}

}

}

return count;

}

}

**总结：O(n^2) n square

解题思路和3SUM一样，也是先对整个数组排序，然后一个外层循环确定第一个数，然后里面使用头尾指针left和right进行夹逼，得到三个数的和。如果这个和大于或者等于目标数，说明我们选的三个数有点大了，就把尾指针right向前一位（因为是排序的数组，所以向前肯定会变小）。如果这个和小于目标数，那就有right - left个有效的结果。为什么呢？因为假设我们此时固定好外层的那个数，还有头指针left指向的数不变，那把尾指针向左移一直到左移到固定的那个数的那一位，这些组合都是小于目标数的。