单链表删除倒数第k个节点

妖狐艹你老母 2022-07-24 10:18 169阅读 0赞

## 单链表删除倒数第k个节点 ##

题目：  
删除单链表中倒数第k个节点

--------------------

## 解题思路及算法代码： ##

标尺法，定义两个指针指向链表头结点，先让一个走k步，然后两个指针同时开始走，当先走的指针走到末尾时，后走的指针指向的结点就是需要删除的结点。

--------------------

单链表结构定义：

typedef struct Node
    {
        int data;
        struct Node* next;
    }node, *pLinkedList;

--------------------

**删除倒数第K结点操作代码**：

//head表示头结点
    Node* removeLastKthNode(pLinkedList head, int k)
    {
        if (NULL == head->next || k < 1)
            return head;
    
        pLinkedList cur = head; //1号指针
        pLinkedList ret = head; //2号指针，指向待删除节点
        pLinkedList pre = NULL; //pdel待删除节点的前一个节点
        /*
        head    1    2    3    4    5
        cur
        ret    
        */
        while (k > 0 && cur != NULL)
        {
            k--;
            cur = cur->next;
        }
    
        //当链表走到终点时，k仍然大于0，可知k值大于链表长度
        if (k > 0 && cur == NULL)
        {
            cout << "k值大于链表长度" << endl;
            return head;
        }
    
        //k == 0时，1号指针和2号指针同时走,ret即为待删除的节点
        if (k == 0)
        {
            while (cur != NULL)
            {
                pre = ret;
                cur = cur->next;
                ret = ret->next;
            }
            /*k = 2时
            head    1       2     3       4     5    NULL
                                 pre     ret         cur
            即要求删除ret节点
            */
            pre->next = ret->next;
            free(ret);
            ret = NULL;
    
            return head;
        }
    }