Given a linked list, remove the n-th node from the end of list and return its head.
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.
Follow up:
Could you do this in one pass?
解法一 Two pass:
//7ms public ListNode removeNthFromEnd(ListNode head, int n) { int length = 0; ListNode temp = head;//do not change head while(temp!=null){ length++; temp = temp.next; } n = length-n+1;//正数第几个 ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode prev = dummyHead; for(int i = 0;i<n-1;i++){ System.out.println(i); prev = prev.next; } prev.next = prev.next.next; return dummyHead.next; }解法二： One pass
public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummyHead = new ListNode(0); dummyHead.next = head; ListNode slow = dummyHead, fast = dummyHead; //让fast先走n+1步 for(int i=1; i<=n+1; i++) { fast = fast.next; } //当fast==null时,我们希望slow是previous node of the toPop,即slow是倒数第n+1个node。此时[slow,fast]共有n+2个node //那么,slow和fast差距是不变的,slow起始位置为dummyHead,所以fast起始位置应为第n+1个node. 所以要让fast先走n+1步 while(fast != null) { slow = slow.next; fast = fast.next; } //删除倒数第n个node slow.next = slow.next.next; return dummyHead.next; }
