19. Remove Nth Node From End of List

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?

My Solution(92ms 22.5MB)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        ListNode ret = new ListNode(0);
        ret.next = head;
        ListNode temp = head;
        int length = 0;
        while(temp != null)
        {
            temp = temp.next;
            length += 1;
        }
        length -= n;
        temp = head;
        if (length == 0)
        {
            if (head.next == null)
            {
                return null;
            }
            else
            {
                ret.next = head.next;
            }
        }
        else
        {
            for(int i = 0; i < length - 1; i++)
            {
                temp = temp.next;
            }
            temp.next = temp.next.next;
        }
        return ret.next;
    }
}

No.1 Solution(88ms)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode RemoveNthFromEnd(ListNode head, int n) {
        if(head==null)
            return head;
        
        ListNode preDeleted;
        ListNode dummy=new ListNode(0);
        dummy.next=head;
        preDeleted=dummy;
        
        for(int index=0;index<n;index++)
        {
            if(head==null)
                return null;
            
            head=head.next;
        }
        
        while(head!=null)
        {
            preDeleted=preDeleted.next;
            head=head.next;
        }
        
        preDeleted.next=preDeleted.next.next;
        
        
        return dummy.next;
    }
}

Things to improve

I should handle null value early in the first loop to increase speed

Leave a Reply

Your email address will not be published. Required fields are marked *