###### tags: `Leetcode` `easy` `list` `python` `c++` `Top 100 Liked Questions`

# 206. Reverse Linked List

## [題目來源:] https://leetcode.com/problems/reverse-linked-list/

## 題目:
Given the head of a singly linked list, reverse the list, and return the reversed list.

Follow up: A linked list can be reversed either **iteratively or recursively**. Could you implement both?

#### [圖片來源:] https://leetcode.com/problems/reverse-linked-list/

## 解題想法:

如圖:
pre斷後，cur指向前方，head往回指pre

## Python(Iterative & Recursive):

class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    def insert(self,node):
        if self.next==None:
            self.next=ListNode(node)
        else:
            self.next.insert(node)
    def printList(self):
        res=[]
        head=self
        while head:
            res.append(head.val)
            head=head.next
        print(res)

class SolutionIt(object):
    def reverseList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #Iterative
        pre=None
        cur=None
        while head:
            cur=head.next
            head.next=pre
            pre=head
            head=cur
        return pre
            
class SolutionRe(object):
    def reverseList(self, head ,pre=None):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        #Recursive:
        if not head:
            return pre
        cur=head.next
        head.next=pre
        return self.reverseList(cur,head)

head=ListNode(1)
head.insert(2)
head.insert(3)
head.insert(4)
head.insert(5)
head.printList()
It=SolutionIt()
iterative=It.reverseList(head)
print("Iterative: ", end=" ")
iterative.printList()

head2=ListNode(1)
head2.insert(2)
head2.insert(3)
head2.insert(4)
head2.insert(5)
head2.printList()
Re=SolutionRe()
recursive=Re.reverseList(head2,None)
print("Recursive: ",end=" ")
recursive.printList()

## C++(Iterative & Recursive):

#include<iostream>
#include<vector>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
    ListNode(): val(0), next(nullptr) {}
    ListNode(int x): val(x), next(nullptr) {}
    ListNode(int x, ListNode *next): val(x), next(next) {}
};

void InsertNode(ListNode *head, int data){
    ListNode *tail=head;
    if (tail->next==nullptr){
        ListNode *new_node= new ListNode(data);
        tail->next=new_node;
    }
    else
        InsertNode(tail->next,data);
}

void PrintList(ListNode *head){
    vector<int> res;
    ListNode *tail=head;
    while (tail!=nullptr){
        res.push_back(tail->val);
        tail=tail->next;
    }
    for (int i=0; i<res.size(); i++){
        cout<<res[i]<<" ";
    }
    cout<<endl;
}

class SolutionIt {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *pre=nullptr;
        ListNode *cur=nullptr;
        while (head!=nullptr){
            cur=head->next;
            head->next=pre;
            pre=head;
            head=cur;
        }
        return pre;
    }
};

class SolutionRe {
public:
    ListNode* reverseList(ListNode* head, ListNode* pre=nullptr) {
        if (head==nullptr)
            return pre;
        ListNode *cur=head->next;
        head->next=pre;
        return reverseList(cur,head);
    }
};

int main(){
    ListNode *head1=new ListNode(1);
    InsertNode(head1,2);
    InsertNode(head1,3);
    InsertNode(head1,4);
    InsertNode(head1,5);
    PrintList(head1);
    SolutionIt It;
    ListNode *iterative = It.reverseList(head1);
    cout<<"Reverse by Iterative:";
    PrintList(iterative);

    ListNode *head2=new ListNode(1);
    InsertNode(head2,2);
    InsertNode(head2,3);
    InsertNode(head2,4);
    InsertNode(head2,5);
    PrintList(head2);

    SolutionRe Re;
    ListNode *recursive = Re.reverseList(head2);
    cout<<"Reverse by Recursive:";
    PrintList(recursive);
}