Question:

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.

Thinking:

  • Method:
    1. Iterate to get the length of the list.
    2. Iterate again to remove
    3. Trick: Use a dummy node to represent the head. ```Java /**
    • Definition for singly-linked list.
    • public class ListNode {
    • int val;
    • ListNode next;
    • ListNode(int x) { val = x; }
    • } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode result = new ListNode(0); result.next = head; int len = 0; ListNode temp = result; while(temp.next != null){ temp = temp.next; len ++; } if (len < n) return null; int index = len + 1 - n; len = 0; temp = result; while(temp.next != null){ len ++; if(len == index){ temp.next = temp.next.next;//Remove return result.next; } temp = temp.next; } return result.next; } } ```

二刷

  1. 快慢指针，先确定两个指针之间的距离。
  2. 同时向后移动指针，定位出倒数第n个结点。
  3. 通过改变next指针删除元素。
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode fast = head, slow = head;
        for(int i = 0; i < n + 1; i++)
            fast = fast.next;
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}