在遍歷列表時(shí)修肠，將當(dāng)前節(jié)點(diǎn)的 next 指針改為指向前一個(gè)元素秫逝。由于節(jié)點(diǎn)沒有引用其上一個(gè)節(jié)點(diǎn)恕出，因此必須事先存儲其前一個(gè)元素。在更改引用之前违帆，還需要另一個(gè)指針來存儲下一個(gè)節(jié)點(diǎn)浙巫。不要忘記在最后返回新的頭引用！
/**
* 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ù)雜度分析
時(shí)間復(fù)雜度：O(n)刷后，假設(shè) n 是列表的長度的畴，時(shí)間復(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;
}
時(shí)間復(fù)雜度：O(n)，假設(shè) n 是列表的長度含衔，那么時(shí)間復(fù)雜度為 O(n)煎娇。
空間復(fù)雜度：O(n)，由于使用遞歸贪染，將會使用隱式椈呵海空間。遞歸深度可能會達(dá)到 n 層杭隙。
