【C语言】单链表的相关热点面试题（包括：从尾到头打印，逆置，冒泡，寻找中间节点，倒数k节点）

1. 从尾到头打印单链表
   

void FromTailToHeadPrint(SListNode*& head)
{
    stack<SListNode*> s;
    SListNode* cur = head;
    while (cur)
    {
        s.push(cur);
        cur = cur->_next;
    }

    while (!s.empty())
    {
        cout << s.top()->_data <<"->";
        s.pop();
    }
    cout << ""<<endl;
}

2.删除一个无头单链表的非尾节点

void Erase(SListNode*& head,SListNode* pos)
{
    //分情况：空节点、一个节点、两个节点、三个节点
    if (head == NULL || pos==NULL)
    {
        return;
    }
    
    if (head == pos)
    {
        free(head);
        head = NULL;
        return;
    }

    SListNode* cur = head;
    while (cur)
    {
        SListNode* next = cur->_next;
        
        if (next == pos)
        {
            //若只有两个节点，pos=next,nextnext=NULL，cur->_next = nextnext;
            //（即使题设未说明删除非尾节点）依然可以删除成功。
            SListNode* nextnext = next->_next;
            cur->_next = nextnext;
            free(next);
            next = NULL;
        }
        cur = cur->_next;
    }
}

3.逆置、反转单链表

void Reverse(SListNode*& head)
{
    if (head == NULL)
    {
        return;
    }
    SListNode* cur = head;
    SListNode* next = NULL;
    while (cur)
    {
        SListNode* tmp = cur;
        cur = cur->_next;
        tmp->_next = next;
        next = tmp;
        head = tmp;
    }
}

4.单链表冒泡排序

void BubbleSort(SListNode*& head)
{
    //空节点或一个节点直接返回
    if (head == NULL || head->_next == NULL)
    {
        return;
    }
    
    SListNode* begin = head;
    SListNode* cur = head;

    while (begin->_next)
    {        
        while (cur->_next)
        {
            if (cur->_data > cur->_next->_data)
            {
                swap(cur->_data, cur->_next->_data);
            }
            cur = cur->_next;
        }
        begin = begin->_next;
    }
}

5.查找单链表的中间节点，要求只能遍历一次链表

SListNode* FindMiddle(SListNode*& head)
{
    if (head == NULL)
    {
        return NULL;
    }
    SListNode* slow = head;
    SListNode* fast = head;

    while (fast->_next)
    {
        if (fast->_next)
        {
            fast = fast->_next;
            if (fast->_next)
            {
                fast = fast->_next;
            }
            else
            {
                return slow;
            }
            slow = slow->_next;
        }
        else
        {
            return NULL;
        }
    }
    
    return slow;
}

6.查找单链表的倒数第k个节点，要求只能遍历一次链表

SListNode* FindLastK(SListNode*& head,int k)
{
    assert(k > 0);
    if (head == NULL)
    {
        return NULL;
    }
    SListNode* slow = head;
    SListNode* fast = head;
    while (k--)
    {
        if (fast->_next)
        {
            fast = fast->_next;
        }
        else
        {
            return NULL;
        }
    }
    slow = slow->_next;
    while (fast->_next)
    {
        fast = fast->_next;
        slow = slow->_next;
    }
    return slow;
}