翻转链表

解决方式（1）：

• 逐个断开原链表的每个节点（保存下个节点）
• 将断开的节点连接到反转链表的表头上
• 更新反转链表的表头
• 回到原链表的下个节点

class Solution {
public:
    /**
     * @param head: n
     * @return: The new head of reversed linked list.
     */
    ListNode * reverse(ListNode * head) {
        // write your code here
        //新建一个用于返回的头p，
        ListNode* p=nullptr,*tmp;
            while(head){
                tmp=head->next;
                head->next=p;
                p=head;
                head=tmp;
            }
        return p;
        
    }
};

方式（2）：
借助栈
用栈先进后出的特点，将每个节点按顺序存入栈中，再从顶到底连接栈中的每个节点
注意倒数第二行代码 p->next=nullptr！！！要将翻转后的最后一个节点（即原链表的第一个节点）的next置为nullptr，不然后果可想而知~

ListNode * reverse(ListNode * head) {
        // // write your code here
        // //新建一个用于返回的头
        // ListNode* p=nullptr,*tmp;
        //     while(head){
        //         tmp=head->next;
        //         head->next=p;
        //         p=head;
        //         head=tmp;
        //     }
        // return p;
        
        std::stack<ListNode *> stk;
        ListNode *reverseHead=new ListNode,*p=reverseHead,*tmp;
        while(head)
        {
            stk.push(head);
            head = head->next;
        }
        
        while(!stk.empty())
        {
            tmp = stk.top();
            p->next = tmp;
            stk.pop();
            p = p->next;
        }
        //最尾部添加null
        p->next = nullptr;
        //释放一开始作为头的部分
        tmp = reverseHead;
        reverseHead = reverseHead->next;
        delete tmp;
        
        return reverseHead;
        
    }