单链表反转(四种方式实现)

题目:

输入一个单链表,反转该链表并输出

输入:

1->2->3->4->5

输出:

5->4->3->2->1

代码示例:

//就地反转
ListNode * reverse1(ListNode *node)
{
    if (node == nullptr)
    {
        return node;
    }
    ListNode *head = new ListNode(-1);
    head->next = node;
    ListNode *curNode = node;
    ListNode *nextNode = curNode->next;
    while (nextNode != nullptr) {
        curNode->next = nextNode->next;
        nextNode->next = head->next;
        head->next = nextNode;
        nextNode = curNode->next;
    }
    return head->next;
}
//头插法
ListNode * reverse2(ListNode *node)
{
    ListNode *preNode = new ListNode(-1);
    ListNode *pCur = node;
    while (pCur != nullptr) {
        ListNode *pNext = pCur->next;
        pCur->next = preNode->next;
        preNode->next = pCur;
        pCur = pNext;
    }
    return preNode->next;
}
//迭代
ListNode * reverse3(ListNode *node)
{
    ListNode *prev = nullptr;
    while(node != nullptr){
        ListNode *tmpNode = node->next;
        node->next = prev;
        prev = node;
        node = tmpNode;
    }
    return prev;
}
//递归
ListNode * reverse4(ListNode *node)
{
    if(node == nullptr|| node->next == nullptr)
    {
        return node;
    }
    ListNode *prev = reverse4(node->next);
    node->next->next = node;
    node->next = nullptr;
    return prev;
}
//创建初始化链表
ListNode * createListNode()
{
    ListNode *head = nullptr;
    ListNode *node1 = new  ListNode(1);
    ListNode *node2 = new  ListNode(2);
    ListNode *node3 = new  ListNode(3);
    ListNode *node4 = new  ListNode(4);
    ListNode *node5 = new  ListNode(5);
    head = node1;
    node1->next = node2;
    node2->next = node3;
    node3->next = node4;
    node4->next = node5;
    node5->next = nullptr;
    ListNode *newHead = reverse(head);
    while (newHead != nullptr)
    {
        qDebug() << newHead->val;
        newHead = newHead->next;
    }
}

上一篇:LeetCode143——ReorderList——3 alorithms combination


下一篇:FreeRTOS与RT-Thread对于中断及临界区的处理