leetCode真題

206. 反轉鏈表

屬于基礎簡單題目

常見的做法有遞歸和while循環

遞歸

    // 1. 遞歸參數和返回值public static ListNode reverseList(ListNode head) {// 1. 遞歸終止條件if (head == null || head.next == null) {return head;}// 遞歸邏輯ListNode last = reverseList(head.next);// last是未反轉鏈表的最后一個節點head.next.next = head;// head和last構成雙向head.next = null;// head的向last的指向取消return last;}

不要用自己的大腦想象遞歸過程，人的大腦記不住幾個棧！

這段代碼我們要分析其中的實現邏輯

1. 我們要反轉整個鏈表（head節點），就要先反轉鏈表的子鏈表（head.next），然后將head修改到整個鏈表的第一個位置（head.next.next = head;head.next = null;）

2. 而要反轉子鏈表head.next，就需要反轉head.next的子鏈表，也就是head.next.next

3. ……直到head.next為null時，此時整個子鏈表只有一個節點（節點5），單獨的一個節點顯然已經完成了反轉，此時直接return返回,return返回之后，head指向4節點，last指向5節點

4. 然后是反轉倒數第二個節點（4），4節點的子鏈表顯然已經完成了反轉，此時只要將4節點拼接到5節點之后即可完成4，5節點的反轉
   head.next.next = head;
   

head.next = null;

return last;

5. head指向3節點，重復第四步，直到最后整個鏈表完成反轉

測試demo

ListNode類

public class ListNode {public int val;public ListNode next;public ListNode() {}public ListNode(int val) {this.val = val;}public ListNode(int val, ListNode next) {this.val = val;this.next = next;}public void loop(ListNode head) {while (head != null) {System.out.print(head.val + "  ");head = head.next;}}
}

反轉實現

public class ListTest {public static void main(String[] args) {ListNode _5 = new ListNode(5);ListNode _4 = new ListNode(4, _5);ListNode _3 = new ListNode(3, _4);ListNode _2 = new ListNode(2, _3);ListNode head = new ListNode(1, _2);System.out.print("====反轉前：");head.loop(head);System.out.println();head = reverseList1(head);System.out.print("====反轉后：");head.loop(head);System.out.println();}// 1. 遞歸參數和返回值public static ListNode reverseList1(ListNode head) {// 1. 遞歸終止條件if (head == null || head.next == null) {return head;}// 遞歸邏輯ListNode last = reverseList1(head.next);// last是未反轉鏈表的最后一個節點head.next.next = head;// head和last構成雙向head.next = null;// head的向last的指向取消return last;}
}

while循環

使用遞歸的好處是，代碼簡潔，但是當鏈表數量特別大的時候，遞歸可能會引起java的虛擬機棧棧溢出

我們提出了第二種方法，就是while循環

	public static ListNode reverseList2(ListNode head) {// head節點拷貝，pre和later節點用于暫存cur節點的前節點和后節點ListNode pre = null, cur = head, later = null;while (cur != null) {// cur節點代表了要反轉的節點，cur節點為null說明所有節點反轉完畢later = cur.next;// 1. later節點指向下一節點cur.next = pre;// 2. cur節點的next節點指向pre節點pre = cur;// 3. pre節點指向cur節點cur = later;// 4. cur節點指向later節點}return pre;}

1. ListNode pre = null, cur = head, temp;
   head節點拷貝，pre和later節點用于后續暫存cur節點的前節點和后節點

2. while (cur != null) {}

cur節點代表了要反轉的節點，cur節點為null說明所有節點反轉完畢

3. later = cur.next;
   記錄cur節點的后節點later

4. cur.next = pre;（最核心的一步）

有人此時會說了，pre不是null嗎，為什么不能直接cur.next = null;呢？

這行代碼的真正含義是新增一條反向的路徑，只是第一個節點反轉的時候pre恰好為null

5. pre = cur;
   記錄要反轉的節點的上一個節點
   

6. cur = temp;
   相當于cur = cur.next，cur節點遍歷到下一個節點位置

7. 重復上述6步
   
   
   
   
   反轉節點3
   

測試demo

同上

總結

遞歸的代碼邏輯清晰，但是消耗內存會比較多，而且可能會棧溢出；
while循環不會棧溢出；

兩者的時間復雜度都是O(n)級別的