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.

用两个指针,两个之间相差n,然后同时向后,让后一个指针到结尾时,前一个指针正好指向要删除的那个node,

注意要处理如果要删除的node正好是head的情况。


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

Second Submission:

Notice, the head pointer should point to the node before the node you would like to delete.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode helper = new ListNode (-1);
        helper.next = head;
        ListNode tail = head;
        head = helper;
        for (int i = 0; i &lt; n - 1; i++) {
            tail = tail.next;
        }
        while(tail.next != null) {
            tail = tail.next;
            head = head.next;
        }
        //remove the head
        head.next = head.next.next;
        return helper.next;
    }
}

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s