反转链表

方法一：双链表——创建一个新链表，倒序链接，形成反转链表

public class Solution {
    public ListNode ReverseList(ListNode head) {
        //空链表
        ListNode newHead = null;
        //遍历原链表
        while(head!=null){
            //头结点将移动，需要保存下一个结点
            ListNode temp = head.next;
            //结点往前累积，形成倒序
            head.next = newHead;
            //移动新结点指针到链表头部
            newHead = head;
            //原链表head指针移动到下一个位置
            head = temp;                  
        }
        return newHead;
    }
}

方法二：利用栈先进后出的性质反转链表

使用了额外空间，空间复杂度 O(n)

• 注意：出栈过程结束后一定要将活动指针的next置为null，否则反转后的链表会陷入循环

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head==null)return null;
        Stack s = new Stack();
        ListNode cur = head;
        while(cur!=null){
            s.push(cur);
            cur = cur.next;
        }
        if(s.size()==1)return head;
        ListNode firstNode = s.pop();
        ListNode res = firstNode;
        while(s.size()!=0)
        {
            res.next = s.pop();
            res = res.next;
        }
        res.next = null;//这一句至关重要！
        return firstNode;
    }
}