反轉鏈表

力扣第206題

我們不只是簡單的學習（背誦）一個數(shù)據(jù)結構，而是要分析他的思路，以及為什么要有不同的指針等等

非遞歸方式：

思路分析：首先要鏈表有個頭指針沒有任何問題

然后，我們要將1的下一個節(jié)點指向空，這樣才能將其反轉過來，但是這個時候我們發(fā)現(xiàn)和下一個節(jié)點2失去了聯(lián)系

所以我們要有一個指針，在1還沒有將next指向空前，記錄下2的位置。所以我們用一個next指針記錄2。并為了好理解，將head改名為cur代表當前節(jié)點。

因此，我們只要將cur的指向下一個節(jié)點的指針指向空之后，便將cur和next指針同時向后移動。

不過這樣我們發(fā)現(xiàn)，我們cur和前面的節(jié)點失去了聯(lián)系，就不能將節(jié)點2指向1了，所以我們還要有一個指針負責記錄前一個節(jié)點，我們就叫它pre吧，那么再來考慮pre指針最開始應該放在哪呢，其實只要指向最左邊的那個NULL就好了。

因此我們剛剛是將1指向NULL，現(xiàn)在改成將cur指向pre即可，就像這樣。

然后我們就可以將這三個指針都向后移動，重復上一步和本步操作，直到cur為null結束即可。

遞歸方式：

首先是寫出遞歸的最后答案，也就是所謂的遞歸出口，毫無疑問是返回第一個節(jié)點head

if (head == null || head.next==null)
 ? ? return head;

再調用一次遞歸函數(shù)

reverseListRecursive(head.next);

直接從宏觀的角度上看，肯定是將head.next之后的所有節(jié)點都反轉過來了，就像下圖所示，其中1被擋住了不要在意。

重點來了，如何將最后的節(jié)點2指向節(jié)點1，并將節(jié)點1指向空？

其實用兩行代碼實現(xiàn)即可，將head.next（節(jié)點2）.next（NULL）指向節(jié)點1，也就是 = head即可

然后再將節(jié)點1指向空，也即head.next = null;

 head.next.next = head;
 head.next = null;

力扣答案總結：

我們來具體實現(xiàn)一下吧，其中的reverseList內的代碼即是力扣答案文章來源地址http://www.zghlxwxcb.cn/news/detail-449664.html

/**
 * @Author: 翰林猿
 * @Description: 反轉鏈表
 **/
public class ReverseListNode {
 ? ?//非遞歸方式
 ? ?public ListNode reverseList(ListNode head) {
 ? ? ? ?//初始化三個指針,其中l(wèi)atter要在過程中指定，因為有可能cur為空，導致latter為空
 ? ? ? ?ListNode pre = null;
 ? ? ? ?ListNode cur = head;
 ? ? ? ?while (cur != null) {
 ? ? ? ? ? ?ListNode latter = cur.next;
 ? ? ? ? ? ?//將cur指向pre
 ? ? ? ? ? ?cur.next = pre;
 ? ? ? ? ? ?//三個指針都向后移動,其中pre和cur在這里移動，latter在第一句會自行移動。
 ? ? ? ? ? ?pre = cur;
 ? ? ? ? ? ?cur = latter;
 ? ? ?  }
 ? ? ? ?return pre;
 ?  }
 ? ?//遞歸方式
 ? ?public ListNode reverseListRecursive(ListNode head) {
 ? ? ? ?if (head == null || head.next==null)
 ? ? ? ? ? ?return head;
 ? ? ? ?ListNode rev = reverseListRecursive(head.next); ? ? //最后會獲取到head
 ? ? ? ?head.next.next = head;
 ? ? ? ?head.next = null;
 ? ? ? ?return rev;
 ?  }
 ? ?public static void main(String[] args) {
 ? ? ? ?ListNode head = new ListNode(1);
 ? ? ? ?head.next = new ListNode(2);
 ? ? ? ?head.next.next = new ListNode(3);
 ? ? ? ?head.next.next.next = new ListNode(4);
 ? ? ? ?head.next.next.next.next = new ListNode(5);
?
 ? ? ? ?ListNode node = new ReverseListNode().reverseList(head);
 ? ? ? ?System.out.println("反轉后的第一個節(jié)點值應當為5 = "+node.val);
?
 ? ? ? ?ListNode node2 = new ReverseListNode().reverseListRecursive(head);
 ? ? ? ?System.out.println("遞歸反轉后的第一個節(jié)點值應當為5 = "+node.val);
 ?  }
}
?
?
class ListNode {
 ? ?int val;
 ? ?ListNode next;
 ? ?ListNode() {
 ?  }
 ? ?ListNode(int val) {
 ? ? ? ?this.val = val;
 ?  }
 ? ?ListNode(int val, ListNode next) {
 ? ? ? ?this.val = val;
 ? ? ? ?this.next = next;
 ?  }
}

到了這里，關于反轉鏈表 Java版 圖文并茂思路分析帶答案（力扣第206題）的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！