删除list倒数第n个元素

题目：有一个链表，删除倒数第n个节点，并返回该链表的头节点。

例如：由一个链表  1->2->3->4->5, 设n = 2.

那么删除倒数第二个节点后 就是1->2->3->5.

 

注意:1.n总是合法的；

2.只遍历一次

链表的结构如下：

 

public class ListNode {
	public int val;
	public ListNode next;

	public ListNode(int x) {
		val = x;
		next = null;
	}
}

 思路是：因为要求是遍历一次，我们必须知道这个链表的长度或者知道什么时候到达链表的末尾，常规的思路是遍历一次知道长度，在遍历到长度减去n的地方，如果我们设置两个指针，一个先走n步，第二个和第一个同时出发，当前指针到达最后一个节点，那么后指针到达需要删除的那个节点之前，删除节点即可。特别注意如果删除第一个节点的话，我们需要特别考虑这个问题。（这里的指针是从c++拿出的概念，我实在不知道该说什么比较好）

 

 

 

 

 

public ListNode removeNthFromEnd(ListNode head, int n) {
		ListNode front = head;//前指针
		ListNode back = head;//后指针

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

			front = front.next;
		}
		if (front == null) {  //这个是n为第一个节点的删除，也是特别的需要注意的地方

			head=head.next;
			back=null;
			return head;

		} else {
			while (front.next != null) {
				front = front.next;
				back = back.next;
			}
			back.next = back.next.next;
		}
		return head;

	}