Leetcode（206）-反转链表

反转一个单链表。

示例:

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

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

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

ListNode* reverseList(ListNode* head)

{

    stack<ListNode*> 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);

}

巴特西

Leetcode（206）-反转链表

最新文章

热门文章