Description

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.

Analysis

有两种方法：

1. 先算链表的长度L，再倒推倒数第n个节点删除
2. 双指针

这种题画图比较好做

• 技巧:

1. dummy node指向head
2. 双指针

Solution

第一种方法AC解：
需要一个dummy指针，一个first指针，详见代码

ListNode removeNthFromEnd(ListNode head, int n) {
        // write your code here
        
        int length = 0;
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = head;  // need a first pointer
        while (first != null) {
            first = first.next;
            length++;
        }
      
        first = dummy;
        
        int i = 0;
        while (i < length - n ) {
            first = first.next;
            i++;
        }
        first.next = first.next.next;
        
        return dummy.next;  
    }

Time Complexity: O(L)
Space Complexity: O(1)

第二种做法AC解：

ListNode removeNthFromEnd(ListNode head, int n) {
    // write your code here
    ListNode dummy = new ListNode(0);
    dummy.next = head;
    
    ListNode first = dummy;
    ListNode second = dummy;
        
    int i = 0;
    while (i < n + 1) {
        first = first.next;
        i++;
    }
        
    while (first != null) {
        first = first.next;
        second = second.next;
    }
    
    second.next = second.next.next;
    return dummy.next;
   
}

Time Complexity: O(L)
Space Complexity: O(1)