LintCode 174.删除链表中倒数第n个节点

思路
结合前面一题的思路即可

/**
 * Definition of singly-linked-list:
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *        this->val = val;
 *        this->next = NULL;
 *     }
 * }
 */

class Solution {
public:
    /**
     * @param head: The first node of linked list.
     * @param n: An integer
     * @return: The head of linked list.
     */
    ListNode * removeNthFromEnd(ListNode * head, int n) {
        // write your code here
        if(head == NULL || head->next==NULL)
        {
            return NULL;
        }
        
        ListNode *p = head;
        int numNode = 0;
        while(p != NULL)
        {
            numNode++;
            p = p->next;
        }
        int numDelete = numNode-n;  //找到待删节点的前一个节点
        p = head;
        if(numDelete <= 0)    //要删除第一个节点
        {
            p = p->next;
            return p;
        }
        while(--numDelete)
        {
            p = p->next;
        }
        p->next = p->next->next;
        return head;
    }
};

但是提交的过程中发现了好多坑

只有一个元素
有两个元素
待删除的节点为头结点
以上种种情况的特殊处理

参考程序

/**
* 本参考程序来自九章算法，由 @九章算法 提供。版权所有，转发请注明出处。
* - 九章算法致力于帮助更多中国人找到好的工作，教师团队均来自硅谷和国内的一线大公司在职工程师。
* - 现有的面试培训课程包括：九章算法班，系统设计班，算法强化班，Java入门与基础算法班，Android 项目实战班，
* - Big Data 项目实战班，算法面试高频题班, 动态规划专题班
* - 更多详情请见官方网站：http://www.jiuzhang.com/?source=code
*/ 

class Solution {
public:
    /*
    题意：删除链表中倒数第n个结点，尽量只扫描一遍。
    使用两个指针扫描，当第一个指针扫描到第N个结点后，
    第二个指针从表头与第一个指针同时向后移动，
    当第一个指针指向空节点时，另一个指针就指向倒数第n个结点了
    */
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *res = new ListNode(0);
        res->next = head;
        ListNode *tmp = res;
        for (int i = 0; i < n; i++) {
            head = head->next;
        }
        while (head != NULL) {
            head = head->next;
            tmp = tmp->next;
        }
        tmp->next = tmp->next->next;
        return res->next;
    }
};

LintCode 174.删除链表中倒数第n个节点

相关推荐