题目描述
给定一个链表,删除链表的倒数第 n 个节点,并且返回链表的头结点。
示例:
给定一个链表: 1->2->3->4->5, 和 n = 2.
当删除了倒数第二个节点后,链表变为 1->2->3->5.
解决方案
思路:用两个指针,第一个指针先走n步,第二个指针再开始和第一个指针一起走,当第一个指针走到末尾的时候,第二个指针刚好走到要删除的节点的前一个节点,此时只需要改变它所指向的节点位置就可以了,以下是完整代码
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head->next) return NULL;
ListNode *slow = head;
ListNode *fast = head;
for(int i=0;i<n;++i){
fast =fast->next;
}
if(!fast) return head->next;
while(fast->next != NULL){
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return head;
}
};