题目:
输入一个单链表,反转该链表并输出
输入:
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;
}
}