在遍歷列表時，將當(dāng)前節(jié)點的 next 指針改為指向前一個元素。由于節(jié)點沒有引用其上一個節(jié)點，因此必須事先存儲其前一個元素。在更改引用之前，還需要另一個指針來存儲下一個節(jié)點。不要忘記在最后返回新的頭引用！

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while(head!=null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

復(fù)雜度分析
時間復(fù)雜度：O(n)，假設(shè) n 是列表的長度，時間復(fù)雜度是 O(n)。
空間復(fù)雜度：O(1)。

遞歸，來自官方題解

public ListNode reverseList(ListNode head) {
    if (head == null || head.next == null) return head;
    ListNode p = reverseList(head.next);
    head.next.next = head;
    head.next = null;
    return p;
}

時間復(fù)雜度：O(n)，假設(shè) n 是列表的長度，那么時間復(fù)雜度為 O(n)。
空間復(fù)雜度：O(n)，由于使用遞歸，將會使用隱式?？臻g。遞歸深度可能會達(dá)到 n 層。