每周一道算法题(十五)

本周的题目难度级别是‘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;
}

版权声明：本文为 Crazy Steven 原创出品，欢迎转载，转载时请注明出处!