【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;
}