题解 | #删除链表的倒数第n个节点#

核心思想

解法3： 三刷用快慢指针一遍写过

• 快慢指针定位
• 对删除首节点，需要用定义新结点的方式来进行特殊处理

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    // 空
    if(head == NULL)
    {
       return head;
    }
    
    
    struct ListNode newNode = {0};
    struct ListNode * pre = &newNode;
    struct ListNode * fast = head;
    struct ListNode * slow = head;
    pre->next = head;

    int i = 0;
    for (; i < n; i ++)
    {
        if(fast == NULL)
        {
            return head;
        }
        
        fast = fast->next;
    }
    
    if(fast == NULL && i == n)
    {
        pre->next = head->next;
        return pre->next;
    }
    
    
    while(fast->next != NULL)
    {
        fast = fast->next;
        slow = slow->next;
    }
    
    
    slow->next = slow->next->next;
    
    return head;
}

解法1：

• 递归
• 考虑几种特殊场景
  1. 空指针
  2. 单节点，且删除
  3. 多结点删除第一个元素

自创

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) 
{
    // case1：空链表 
    if(head == NULL || n == 0)
    {
        return head;
    }
    
    // case2: 单节点链表
    // 非空链表的
    static int list_len = 0;
    static int count = 0;
    if(list_len == 0)
    {
        struct ListNode * temp = head;
        while(temp != NULL)
        {
            temp = temp->next;
            list_len++;
        }
    }

    if(list_len == 1 && n == 1)
    {
        return NULL;
    }
    
    if(list_len == n)
    {
        return head->next;
    }
    // 终结条件,尾结点了
    if(head->next == NULL)
    {
        return head;
    }
    
    struct ListNode * tail = NULL;
    tail = removeNthFromEnd(head->next, n);
    count++;
    if(count == n)
    {
        head->next = tail->next;
    }
    
    return head;
}

解法2：

• 求长度 len
• 对特殊场景处理
  • 空链表， n=0
• 正向遍历到第 index = len - n
• 摘掉节点
  • n == 1，return head->next
  • n != 1, move->next = move->next->next;
• return head

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 * };
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param head ListNode类 
 * @param n int整型 
 * @return ListNode类
 */
struct ListNode* removeNthFromEnd(struct ListNode* head, int n ) {
    // write code here
    int len = 0;
    struct ListNode * move = head;
    while(move != NULL)
    {
        move = move->next;
        len++;
    }

    if(len < 1 || n == 0)
    {
        return head;
    }
    
    // 删除首节点，特殊处理
    if(len == n)
    {
        return head->next;
    }
    
    int i = 1;
    int index = len -n;
    move = head;
    while(move != NULL)
    {
        if(i == index)
        {
            break;
        }
        i++;
        move = move->next;
    }

     // 特殊处理， 最后一个节点
    if(n == 1)
    {
        move->next = NULL;
    }
    else
    {
        move->next = move->next->next;
    }
    
    return head;
}