Leetcode(206)-反转链表
阅读原文时间:2023年07月11日阅读:3

反转一个单链表。

示例:

输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路:反转链表很简单,经常使用stack的,一下子就会想到用stack存储链表的节点,然后反向输出

ListNode* reverseList(ListNode* head)
{
stack s;
ListNode* p=head,*newhead,*pnew;
newhead=NULL;
while(p)
{
s.push(p);
p=p->next;
}
while(!s.empty())
{
if(newhead==NULL)
{
newhead=pnew=s.top();
s.pop();
}
else
{
pnew->next=s.top();
s.pop();
pnew=pnew->next;
}
}
if(newhead)
pnew->next=NULL;
return newhead;
}

另外还有一种递归的方式

ListNode *reverseList(ListNode *head,ListNode *pNewHead)
{
if(head == NULL)
return pNewHead;
ListNode *next = head->next;
head->next = pNewHead;
return reverseList(next,head);
}
ListNode* reverseList(ListNode* head) {
return reverseList(head,NULL);
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章