19. Remove Nth Node From End of List(C++,Python)

 1 Given a linked list, remove the nth node from the end of list and return its head.
 2 
 3 For example,
 4 
 5    Given linked list: 1->2->3->4->5, and n = 2.
 6 
 7    After removing the second node from the end, the linked list becomes 1->2->3->5.
 8 Note:
 9 Given n will always be valid.
10 Try to do this in one pass.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     struct ListNode *next;
 6  * };
 7  */
 8 struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
 9     struct ListNode* cur;
10     struct ListNode* pre;
11     cur = head;
12     pre = head;
13     if(head == NULL)
14         return head;
15     while(n)
16     {
17         cur = cur->next;
18         n--;
19     }
20     if(cur == NULL){
21         head = head->next;
22         return head;
23     }
24     while(cur->next != NULL){
25         cur = cur->next;
26         pre = pre->next;
27     }
28     pre->next = pre->next->next;
29     return head;
30     
31 }

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
        """
        #这里的头结点是第一个结点
        #判断链表是否为空
        if head == None:
            return head
        
        #设置两个标志位
        cur = head
        pre = head
        
        #cur先走n步
        while n:
            cur = cur.next
            n -= 1    
            
        #如果cur为空，则说明n为链表长度
        if cur == None:
            return head.next
        
        #pre标志位和cur一起走，直到cur走到最后一个结点
        while cur.next != None:
            cur = cur.next
            pre = pre.next

        #删除倒数第n个结点
        pre.next = pre.next.next
        return head