輸入:1->2->3->4->5->NULL
輸出:5->4->3->2->1->NULL
/**
* Definition for singly-linked list.
* public class ListNode {
*? ? int val;
*? ? ListNode next;
*? ? ListNode(int x) { val = x; }
* }
*/
解法1：
使用while循環(huán)依次變更指針
class Solution {
????public ListNode reverseList(ListNode head) {
????????ListNode now = null;
?????????ListNode temp = null;
????????while(head != null) {
????????????temp = head.next;
????????????head.next = now;
????????????now = head;
????????????head = temp;
?????????}
????????return now;
????}
}
時(shí)間復(fù)雜度 O(n)
now 存儲當(dāng)前節(jié)點(diǎn)head，temp存儲下一節(jié)點(diǎn)next，每次while循環(huán)會將head.next指向上一次循環(huán)時(shí)留下的now运怖，而temp再次更改為當(dāng)前節(jié)點(diǎn)的next
解法2：
使用遞歸
class Solution {
????public ListNode reverseList(ListNode head) {
????????if(head == null || head.next == null){
????????????return head;
????????}
????????ListNode now = reverseList(head.next);
????????head.next.next = head;
?????????head.next = null;
?????????return now;
????}
}
時(shí)間復(fù)雜度O(n)
本質(zhì)是遞歸到最后一個(gè)節(jié)點(diǎn)球订，然后從最后一個(gè)節(jié)點(diǎn)向前反轉(zhuǎn)指針，和解法1本質(zhì)上類似柱彻，只是順序從后往前幽污，
?head.next = null;用來防止死循環(huán)內(nèi)存溢出，now始終為5磨隘，不參與反轉(zhuǎn)
