如何在链表中使用双指针技术

题目：给定一个链表，删除倒数第n个结点。如 1->2->3->4->5->null，n=2，返回 1->2->3->5->null。

需要明确的地方：n从0计还是从1计？n不合法，负数或者大于连标长度如何处理（保证n合法）。

思路1：先遍历一遍计算链表长度，再遍历一遍删除第length-n+1个结点。

思路2：能不能只遍历一遍链表就解决问题呢？首先添加一个虚拟结点，找到要删除结点的前驱。使用双指针，也就是快慢指针。

公用代码：

​ public class ListNode { public int val; public ListNode next; public ListNode(int x) { this.val = x; this.next = null; } public static ListNode createList(int[] nums) { if(null == nums || 0 == nums.length) return null; ListNode head = new ListNode(nums[0]); ListNode needle = head; for(int i = 1; i < nums.length;++i) { ListNode node = new ListNode(nums[i]); needle.next = node; needle = needle.next; needle.next = null; } return head; } }

public ListNode removeNthFromEnd(ListNode head, int n) { if (n < 0) return null; // 创建虚拟头指针 ListNode dummyHead = new ListNode(-1); dummyHead.next = head; ListNode pre = dummyHead; ListNode fast = dummyHead.next; // 快指针先走n步 for (int i = 0; i < n; i++) { if (fast != null) fast = fast.next; } // 快慢指针一同前行，但是这里要对快指针进行判断哦 while (fast != null) { pre = pre.next; fast = fast.next; } // 此时fast指向null，而pre就指向要删除结点的前驱 ListNode delNode = pre.next; pre.next = delNode.next; return dummyHead.next; }