Given a linked list, remove the nth node from the end of list and return its head.
For example,
Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes 1->2->3->5.Note: Given n will always be valid.
Try to do this in one pass.
题目目标：将单链表中倒数第n个元素删除。要求时间复杂度O(n)，且尽量只扫描一次链表。
题目分析：要知道链表最末位的元素才知道倒数第n个是啥啊，所以扫到末位元素已经占据了O(n)的复杂度。为了不再一次扫链表，所以删除操作只能在O(1)时间内完成。在这里我引入一个长度为n+1的缓冲区（这里的n代表是倒数第n个元素），来保存扫描过程中最后出现的n+1个链表节点，可以把这段缓冲看作是循环链表，因为我就是这么做的。
class ListNode { int val; ListNode next; ListNode(int x) { val = x; } } public class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode temp=head; ListNode[] nodepointer=new ListNode[n+1]; //构建缓冲区，要删除倒数第n个元素，必须找到倒数第n+1个才行，所以缓冲大小是n+1 int i=0; for(i=0;temp!=null;i++){ //遍历链表，并将链表元素循环存入缓冲区 nodepointer[i%(n+1)]=temp; temp=temp.next; } if(i-n-1<0)return nodepointer[(i-n)%(n+1)].next; //在遍历完成后i会指向链表末位元素的后一位，即链表最大元素为5的话，i也会变成5(i是从0开始，元素是从1开始).所以如果删除的是首个元素的话(i-n-1<0)，就不用进行链表拼接了，直接返回第二个元素的引用即可，否则进行链表拼接 else { temp=nodepointer[(i-n-1)%(n+1)]; temp.next=temp.next.next; return head; } } } import java.util.Arrays; import java.util.Scanner; /** * @author DELL * */ public class Main{ public static void main(String[] args){ /*Scanner in=new Scanner(System.in); String target=in.nextLine();*/ ListNode listnode=new ListNode(1),temp=null; temp=listnode; for(int i=2;i<=5;i++){ temp.next=new ListNode(i); temp=temp.next; } temp.next=null; long startTime=System.currentTimeMillis(); Solution find=new Solution(); temp=find.removeNthFromEnd(listnode,2); long endTime=System.currentTimeMillis(); long excTime=(long)(endTime-startTime); System.out.println("执行时间："+excTime+"ms"); for(int i=0;temp!=null;i++){ System.out.println(temp.val); temp=temp.next; } } }