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?
Thoughts
- 两个指针(
slow,fast),间隔n - 当
fast到达链表尾端的时候，slow就到了想要删掉的节点， - 删掉slow对应的节点
Code(JAVA)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
// slow-> ... -> fast
// n tail
ListNode dummyHead = new ListNode(0,head);
ListNode slow = dummyHead;
ListNode fast = head;
for(int i = 0; i < n; i++) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummyHead.next;
}
