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

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.

 1 /** 2  * Definition for singly-linked list. 3  * struct ListNode { 4  *     int val; 5  *     ListNode *next; 6  *     ListNode(int x) : val(x), next(NULL) {} 7  * }; 8  */ 9 class Solution {10 public:11     ListNode *removeNthFromEnd(ListNode *head, int n) {12         if( !head || n < 1 ) return head;   //若head为空,或n不合法13         ListNode node(0);   //设置头结点,好删除14         node.next = head;15         ListNode* pre = &node;  //slow的前驱节点16         ListNode* fast = head;17         while( n && fast ) {    //令fast先指向第n个节点18             fast = fast->next;19             --n;20         }21         if( n && !fast ) return head;   //若链表长度没有n大22         ListNode* slow = head;23         while( fast ) { //fast和slow同时后移,slow为空时结束24             fast = fast->next;25             pre = slow;26             slow = slow->next;27         }28         pre->next = slow->next; //删除第n个节点29         delete slow;30         return node.next;31     }32 };

 

设立前后两指针,假设为前指针为fast,后指针为slow,先让fast指针指向head,向后走n步,指向第n个节点,然后slow指针指向head,让fast指针和slow指针同时后移,知道slow为空,那么fast指针指向的就是倒数第n个节点

 

Remove Nth Node From End of List