删除单链表的倒数第k个结点

港控/mmm° 2022-02-01 01:57 211阅读 0赞

**策略**

直接遍历总数为len，再次遍历第len-k+1个就是答案，但是这样遍历了O(N+k)个，可以在O在更短的时间内找到

**图示**

![181644435682162.png][]

**参考代码**

![复制代码][copycode.gif]

#include <iostream>
    using namespace std;
    
    typedef struct ListNode
    {
        int value;
        ListNode* next;
    }ListNode;
    
    void createList(ListNode *&head)
    {
        head = new(ListNode);
        head->value = 1;
        head->next = NULL;
    
        ListNode *p2 = new(ListNode);
        p2->value = 2;
        p2->next = NULL;
        head->next = p2;
    
        ListNode *p3 = new(ListNode);
        p3->value = 3;
        p3->next = NULL;
        p2->next = p3;
    
        ListNode *p4 = new(ListNode);
        p4->value = 4;
        p4->next = NULL;
        p3->next = p4;
    }
    void deleteList(ListNode *p)
    {
        ListNode *next = NULL;
        while(p != NULL)
        {
            next = p->next;
            delete p;
            p = NULL;
            p = next;
        }
    }
    
    
    
    bool deleteKNode_2(ListNode *head, int k)
    {
        if(head == NULL || k <= 0)
            return false;
        ListNode *pre = head;
        for(int i = 0; i < k - 1; ++i)
        {
            if(pre == NULL)
                return false;
            pre = pre->next;
        }
        ListNode *cur = head;
        while(pre->next)
        {
            pre = pre->next;
            cur = cur->next;
        }
        cout << cur->value;
        cout << "succeed:" << endl;
        return true;
    }
    int main()
    {
        ListNode *head = NULL;
        createList(head);
        int k = 8;
        
        cout << "Result:" << deleteKNode_2(head, 2) << endl;
        deleteList(head);
    }

![复制代码][copycode.gif]

**结果**

![181646311462098.png][]

**三点注意**

1. 指针为空

2. k<=0

3. k<len

本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/p/3608117.html，如需转载请自行联系原作者

[181644435682162.png]: /images/20220201/39a73e448e0943aa8d4a56de739cca9f.png
[copycode.gif]: /images/20220201/52db6a81697843a6bbffda69daa7ea34.png
[181646311462098.png]: /images/20220201/058bda1d6dd04a0280c9fbd56db12878.png