19. Remove Nth Node From End of List

Given a linked list, remove the n-th node from the end of list and return its head.

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.

Follow up:

Could you do this in one pass?

解题思路：

设置三个指针pre，q，p。pre指向待删除结点的前驱结点；q指向待删除结点；p为工作指针，首先将p前进N个结点，题目已给出给定的n保证是有效的，此时如果p==null则代表要删除的为头节点，若不为空，将q与p同步遍历链表，pre指向q的前驱，直到p遍历到链表尾，然后s

/* 执行用时 : 8 ms, 在Remove Nth Node From End of List的C提交中击败了95.60% 的用户 内存消耗 : 7.1 MB, 在Remove Nth Node From End of List的C提交中击败了78.96% 的用户 */ /** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n){ struct ListNode* p=head,*q=head,*pre=NULL;//pre记录要删除结点的前驱，q指向要删除结点，p前进n之后再和p一起遍历。p为快指针，先遍历n个结点再遍历到链表尾 int i=0; while(i<n){//题目已给出给定的n保证是有效的，如未保证，则条件应是while(i<n&&p!=NUll) p=p->next;i++; } if(p==NULL)//表明要删除倒数第N个结点，即头结点head。题目已给出给定的n保证是有效的，如未保证，则条件应是if(i==n) { head=head->next; return head; } while(p!=NULL){//找出要删除节点，使pre指向其前驱，q指向此结点 pre=q; q=q->next; p=p->next; } //删除倒数第N个结点 pre->next=q->next; free(q); return head; }

改进：

/* 执行用时 : 4 ms, 在Remove Nth Node From End of List的C提交中击败了98.22% 的用户 内存消耗 : 7.2 MB, 在Remove Nth Node From End of List的C提交中击败了75.23% 的用户 */ struct ListNode* removeNthFromEnd(struct ListNode* head, int n) { struct ListNode *fast = head, *slow = head; //将p，q改为fast，slow，更易理解。没有设置pre指针，节约空间 int i = 0; if(!head->next)//判定特殊情况 { return NULL; } //fast先前进n步 while (i < n) { fast = fast->next; i++; } //判定是否是删除头节点 if(!fast) { head = head->next; } while (fast) { //此处判定条件是fast->next，条件满足时slow指向待删除结点的前驱结点，因此无需用pre指向 if (fast->next == NULL) { slow->next = slow->next->next;//slow指向待删除结点前驱 break; } //同步遍历 fast = fast->next; slow = slow->next; } return head; }

后记：

对特殊情况要仔细设置判定条件，特别是对头节点的删除