逆序单链表（C语言）

先看一下

单链表节点的结构

typedef int DataType;
typedef struct Node
{
    DataType _data;
    struct Node* _next;
}Node, *PNode;

单链表的尾插操作

void SListPushBack(PNode* pHead, DataType data)
{
    PNode _new = NULL;
    // 参数检验
    assert(pHead);

    _new = BuyNewNode(data);
    if (NULL == _new)
    {
        return;
    }
    else
    {
        if (NULL == (*pHead))
        {
            *pHead = _new;
        }
        else
        {
            PNode pCur = NULL;
            pCur = (*pHead);

            while (!(pCur->_next == NULL))
            {
                pCur = pCur->_next;
            }

            pCur->_next = _new;
        }
    }
}

看一个简单的题目

从尾到头打印单链表

思想： 递归
如果当前节点的next域不为空，递归打印next域之后的内容，直到当前节点为空，返回，打印当前节点的值data.

来看代码

// 从尾到头打印单链表 
void PrintSListFromTail2Head(PNode pHead)
{
    if (pHead == NULL)
    {
        printf("NULL");
        return;
    }
    PrintSListFromTail2Head(pHead->_next);

    printf("->%d", pHead->_data);
}

之后我们测试一把

void TestPrintSListFromTail2Head()
{
    PNode pHead = NULL;
    SListPushBack(&pHead, 1);
    SListPushBack(&pHead, 2);
    SListPushBack(&pHead, 3);
    SListPushBack(&pHead, 4);

    printf("positive seq: ");
    PrintNode(pHead);

    printf("inverted seq: ");
    PrintSListFromTail2Head(pHead);
    printf("\n");
}

int main()
{
    TestPrintSListFromTail2Head();
    system("pause");
    return 0;
}

测试结果

单链表逆序

方法一 循环迭代
思想：

使用额外的存储节点pPre, 初始状态下，pPre指向NULL；head指向当前节点
用pNext保存当前节点的next域，此时我们就可以把头节点摘下来，将pPre交给head->_next（相当于把当前节点摘下来了），然后移动head和next指针。

我们发现一次操作不能达到目标，需要循环，循环终止条件head指针为空

最后我们发现pPre里保存的就是逆序后单链表的头指针

之后我们来看代码：

// 逆序单链表
PNode ReverseLink(PNode *head)
{
    PNode _pNext = NULL;
    PNode _pPre = NULL;

    assert(head);

    while ((*head) != NULL)
    {
        _pNext = (*head)->_next;
        (*head)->_next = _pPre;
        _pPre = (*head);
        (*head) = _pNext;
    }

    return _pPre;
}

然后我们来测试一把：

void TestReverse()
{
    PNode pHead = NULL;
    SListPushBack(&pHead, 1);
    SListPushBack(&pHead, 2);
    SListPushBack(&pHead, 3);
    SListPushBack(&pHead, 4);

    printf("positive seq: ");
    PrintNode(pHead);

    printf("inverted seq: ");
    PrintSListFromTail2Head(pHead);
    printf("\n");

    pHead = ReverseLink(&pHead);
    printf("After Renerse: ");
    PrintNode(pHead);
}

int main()
{
    TestReverse();
    system("pause");
    return 0;
}

测试结果

方法二递归
思想：

如果当前节点的next域不为空，就递归逆序next域之后的单链表
递归出口: 单链表只剩下一个节点
回溯的时候，让next域反转过来，这是关键！！！！
来看代码

// 逆序单链表递归
PNode ReverseLinkRcs(PNode *head)
{
    PNode _newNode = NULL;

    assert(head);
    if ((*head) == NULL || (*head)->_next == NULL)
    {
        return (*head);
    }

    _newNode = ReverseLinkRcs(&(*head)->_next); // 递归部分
    (*head)->_next->_next = (*head); // 回溯
    (*head)->_next = NULL;

    return _newNode;

}

测试

void TestReverse()
{
    PNode pHead = NULL;
    SListPushBack(&pHead, 1);
    SListPushBack(&pHead, 2);
    SListPushBack(&pHead, 3);
    SListPushBack(&pHead, 4);

    printf("positive seq: ");
    PrintNode(pHead);

    printf("inverted seq: ");
    PrintSListFromTail2Head(pHead);
    printf("\n");

    pHead = ReverseLinkRcs(&pHead);
    printf("After Renerse: ");
    PrintNode(pHead);
}

int main()
{
    TestReverse();
    system("pause");
    return 0;
}

测试结果

如有不正，还请指出，有劳！