给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。

示例：

给定一个链表: 1->2->3->4->5, 和 n = 2.

当删除了倒数第二个节点后，链表变为 1->2->3->5.
说明：

给定的 n 保证是有效的。

进阶：

你能尝试使用一趟扫描实现吗？

 

 

思路：

即是用一趟扫描找出倒数第k个节点并且删除

先看看另外一个题，找到倒数第k个节点

用两个指针

 

	// 删除链表的倒数第n个 即要找到倒数第n个节点的前一个节点
	public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode first = head;
		ListNode second = head;
		for (int i = 0; i < n - 1; i++) {  //控制走n-1步
			if (first.next == null) {
				return null;
			}
			first = first.next;
		}
		while (first.next != null) { // 此时second来到倒数第n个节点
			first = first.next;
			second = second.next;
		}	
		return second;
	}

 

再看看怎么删除倒数第k个节点，即是要找到倒数第k个节点的前一个节点，并且删除。

这和上面相比，第一趟是走了n步，所以第二趟的时候，能保证少走一步，即让second来到倒数第n个节点的前一个

public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode first = head;
		ListNode second = head;
		for (int i = 0; i < n; i++) {  //控制走n步
			first = first.next;
		}
		if (first == null) { //边界处理
			head=head.next;
			return head;
		}
		while (first.next != null) { // 此时second来到倒数第n个节点的前一个
			first = first.next;
			second = second.next;
		}	
		second.next=second.next.next;
		return head;
	}