反轉鏈表
力扣第206題
我們不只是簡單的學習（背誦）一個資料結構，而是要分析他的思路，以及為什么要有不同的指標等等
非遞回方式：
思路分析：首先要鏈表有個頭指標沒有任何問題
然后，我們要將1的下一個節點指向空，這樣才能將其反轉過來，但是這個時候我們發現和下一個節點2失去了聯系
所以我們要有一個指標，在1還沒有將next指向空前，記錄下2的位置，所以我們用一個next指標記錄2，并為了好理解，將head改名為cur代表當前節點，
因此，我們只要將cur的指向下一個節點的指標指向空之后，便將cur和next指標同時向后移動，
不過這樣我們發現，我們cur和前面的節點失去了聯系，就不能將節點2指向1了，所以我們還要有一個指標負責記錄前一個節點，我們就叫它pre吧，那么再來考慮pre指標最開始應該放在哪呢，其實只要指向最左邊的那個NULL就好了，
因此我們剛剛是將1指向NULL，現在改成將cur指向pre即可，就像這樣，
然后我們就可以將這三個指標都向后移動，重復上一步和本步操作，直到cur為null結束即可，
遞回方式：
首先是寫出遞回的最后答案，也就是所謂的遞回出口，毫無疑問是回傳第一個節點head
if (head == null || head.next==null)
return head;再呼叫一次遞回函式
reverseListRecursive(head.next);直接從宏觀的角度上看，肯定是將head.next之后的所有節點都反轉過來了，就像下圖所示，其中1被擋住了不要在意，
重點來了，如何將最后的節點2指向節點1，并將節點1指向空？
其實用兩行代碼實作即可，將head.next（節點2）.next（NULL）指向節點1，也就是 = head即可
然后再將節點1指向空，也即head.next = null;
head.next.next = head;
head.next = null;力扣答案總結：
我們來具體實作一下吧，其中的reverseList內的代碼即是力扣答案
/**
* @Author: 翰林猿
* @Description: 反轉鏈表
**/
public class ReverseListNode {
//非遞回方式
public ListNode reverseList(ListNode head) {
//初始化三個指標,其中latter要在程序中指定，因為有可能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("反轉后的第一個節點值應當為5 = "+node.val);
?
ListNode node2 = new ReverseListNode().reverseListRecursive(head);
System.out.println("遞回反轉后的第一個節點值應當為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;
}
}轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/552825.html
標籤：其他
上一篇：民間最大社區，倒閉了！
下一篇：返回列表