查找（删除）单链表的倒数第k个结点

系统管理员 2022-05-12 09:42 152阅读 0赞

1.查找单链表的倒数第k个结点（只能遍历一次链表）  
2.删除单链表的倒数第k个结点

对于第一个问题，如果可以两次遍历链表，我们就可以先计算出链表的长度，然后再减去k-1就能求得倒数第k个结点  
但只能遍历一次链表，我们就可以用使用两个指针front，back，让front先走，走k-1个结点，然后再让front和back同时走当front走到最后结点的时候，back就走到了倒数第k个结点  
![这里写图片描述][70]

void Backwords(Node *first, int k)
        {
            assert(first);
            Node *front = first;
            Node *back = first;
            while (--k)
            {
                front = front->next;
            }
            while (front->next != NULL)
            {
                front = front->next;
                back = back->next;
            }
            printf("%d", back->data);
        }

对于第二个问题，无非就是上一个问题的进阶版，先找到倒数第k个结点（注：再次过程中，要把该结点的前一个结点记录下来），然后删除即可，但要注意，如果要删的是头结点尼？这就要另行处理了

void RemoveBackwords(Node **first, int k)
        {
            assert(first); //判断不是空指针
            assert(*first); //判断不是空链表
            int flag = 0;
            Node *front = *first;
            Node *back = *first;
            Node *node = NULL;
            while (--k)
            {
                front = front->next;
            }
    
            while (front->next != NULL)
            {
                front = front->next;
                node = back;
                back = back->next;
                flag = 1;
            }
            //如果flag仍未0，表示要删除的是头结点
            if (flag == 0) 
            {
                *first = (*first)->next;
                free(back);
                return;
            }
            node->next = back->next;
            free(back);
        }

[70]: /images/20220512/8673c993580b49c6b3bc3626f345dbcd.png