206. Reverse Linked List

Reverse a singly linked list.

Example:

Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL

python:

class Solution(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        pre,cur=None,head
        while cur:
            temp=cur.next
            cur.next=pre
            pre=cur
            cur=temp
        return pre
        

C++循环:

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        
        ListNode* first = NULL;
        ListNode* second = head;
        ListNode* third = NULL;
        while(second){
            third = second->next;
            second->next=first;
            first=second;
            second=third;
        }
        return first;
    }
};

栈：

ector<int >printListFromTailToHead(struct ListNode* head)
{
std::stack<ListNode*> nodes;
ListNode* pNode=head;
while(pNode)
{
    nodes.push(pNode);
    pNode=pNode->next;
}
vector<int >res;
while(!nodes.empty())
{
    ListNode* temp=nodes.top();
    res.push_back(temp->val);
    nodes.pop();
}
return res;
}

递归：对当前结点的下一结点做递归，返回倒置后的链表，之后使当前结点的下一结点指向当前结点，当前结点指向NULL。

     ListNode* reverseList(ListNode* head)
     {
         if(head==NULL||head->next==NULL)
            return head;
            
         ListNode * nextNode=head->next;
         ListNode * res=reverseList(head->next);
         nextNode->next=head;
         head->next=NULL;
         return res;
     }