首页 > 代码库 > LeetCode:Remove Nth Node From End of List

LeetCode:Remove Nth Node From End of List

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.
一开始的想法是遍历一遍得到LinkedList的长度,在得到要删除的位置,在删除。
后来看到Note中提到最好只遍历一次。后来的想法是,在一次遍历过程中,在i位置上查看其n个位置后的Node是不是终止结点。如果是则i位置为要删除结点删除就好。

public class Solution {
     public ListNode removeNthFromEnd(ListNode head, int n)
    {
        ListNode start = head;
        ListNode former = head;
        while(!isNextNthNodeEndOfList(start,n))
        {
            former = start;
            start = start.next;
        }
        if(start == former)return start.next;
        former.next = start.next;
        return head;
    }
   
    public boolean isNextNthNodeEndOfList(ListNode node,int n)
    {
        int i = 1;
        ListNode p = node;
        while(i<n)
        {
            p = p.next;
            i++;
        }
        if(p.next == null) return true;
        return false;
       
    }
}