题目

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个

Hints

Related Topics: LinkedList, Two Pointers

通过两个指针 后一个指针在前一个指针移动 n-1 个之后再移动 就能保证该指针是要移除的那个了

代码

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 start = new ListNode(0);

        ListNode slow = start, fast = start;

        slow.next = head;

        for(int i=0;i<=n;i++){

            fast = fast.next;

        }

        while(fast!=null){

            slow = slow.next;

            fast = fast.next;

        }

        slow.next = slow.next.next;

        return start.next;

    }

}

Python

# Definition for singly-linked list.

# class ListNode(object):

#     def __init__(self, x):

#         self.val = x

#         self.next = None

class Solution(object):

    def removeNthFromEnd(self, head, n):

        """

        :type head: ListNode

        :type n: int

        :rtype: ListNode

        """

        t = ListNode(head.val)

        t.next = head

        a = b = c = t

        count = 0

        while a.next!=None:

            a = a.next

            count += 1

            if count>=n:

                c = b

                b = b.next

        c.next = b.next

        head = t.next

        return head