每周一道算法题(十五)
2017-06-24 本文已影响692人
CrazySteven
本周的题目难度级别是‘Medium’
题目：给定一串链表和一个整数n，要求删除链表倒数第n个节点
注：输入的n永远是合法的，试着访问‘一次‘链表就搞定。
其实这道题如果不限制遍历次数，难度级别也就成了EASY，就是因为只能遍历’一次‘，所以难度级别也就上升了。
说下思路，这道题最大的问题就是不知道链表长度，如果知道链表长度，那就很简单了，但是换个想法，正数和倒数的数字其实是和长度有关系的。我们定义两个指针来遍历链表，快的指针先走n-1步，然后快慢指针一起走，当快的指针走到最后一个，慢的指针就走到了倒数第n个节点，然后删除即可。
顺便拓展一下，如何找出中间的节点呢，一样的定义快慢两个指针，慢指针一次走一步，快指针一次走两步，当快指针走到最后，慢指针就走到中间了。同理，如果快指针一次走三步，那走到最后，慢指针就停留在1/3的节点处。
搞定了思路，下面来看看代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
//如果链表只有一个头节点，那么直接返回即可，因为题目说了n一定合法
if (head->next == NULL) return head;
//定义三个指针，都指向头结点
struct ListNode *fast = head;
struct ListNode *slow = head;
struct ListNode *pre = head;
//快指针先走n步
while(--n && fast->next != NULL) fast = fast->next;
//快慢指针一起走
while (fast->next != NULL){
fast = fast->next;
//记录慢指针的前一个节点pre
pre = slow;
slow = slow->next;
}
//如果删除的是投节点，直接返回头节点的下一个节点
if (slow == head) return head->next;
//如果删除的是最后一个节点，则pre节点的下一个节点置为0,否则指向慢指针的下一个节点
pre->next = slow->next == NULL ? 0 : slow->next;
return head;
}
