單連結清單三種反轉方法-Java

文章目錄

• 前言
• 一、單連結清單結構
• 一、單連結清單反轉（從前到後周遊）效率高，推薦
• 二、單連結清單反轉（利用棧）
• 三、單連結清單反轉（利用遞歸）難了解，可以學習學習
• 總結

前言

刷leetcode基礎題的時候用到了單連結清單的反轉，記錄一下反轉方法，并用Java語言實作。

提示：以下是本篇文章正文内容，下面案例可供參考

一、單連結清單結構

1. 首先要明确 單連結清單節點的構成，一般來說節點包括兩個域：
2. 資料域data,   指針域next.。
3. 資料域用來存儲目前節點的資料值，指針域用來存儲目前指針指向的内容。

二、單連結清單反轉（從前到後周遊）效率高、推薦

1. 基本思路：
   1. 連結清單的反轉關鍵就是讓指針域進行變更，
   2. 初始狀态：結點Null→A→B→C→Null 
   3. 需要調整為：結點Null←A←B←C←Null.
   4. 因為最開始是從A開始，是以需要先定義一個連結清單類型的節點 prev,用于存儲目前節點的前置節點。
   5. 再定義一個連結清單類型的節點next，用來臨時存儲目前節點的下一個節點。
   6. 最後return prev結點，因為結點之間有指針連結，是以會輸出反轉後的連結清單。
2. 具體實作(Java)：

   public ListNode reverse(ListNode head){
       ListNode prev = null;//定義一個前置結點。
       while(head != null){
           //這裡要把next放在這裡定義，不提前的原因是需要先滿足head!= null的條件。
           ListNode next = head.next;
           head.next = prev;//調整指針域，讓結點指向前置結點。
           //為下一次做準備
           prev = head;
           head = next;
       }
       return prev;
   }
   /*單連結清單的定義 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
              

三、單連結清單反轉（利用棧）記憶體消耗高，不推薦

1. 基本思路：
   1. 連結清單的反轉關鍵就是讓指針域進行變更，
   2. 初始狀态：結點Null→A→B→C→Null 
   3. 需要調整為：結點Null←A←B←C←Null.
   4. 那麼考慮借助棧後進先出的結構特點，每次讀取一個結點入棧，最後統一出棧建構新的單連結清單。
   5. 得到的單連結清單即為原始單連結清單的反轉。
2. 具體實作（Java）：

   /*單連結清單的定義 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
   public ListNode reverse(ListNode head){
       Stack<Integer> stack = new Stack<>();
       ListNode node = head;
       ListNode prev = null;
       //單連結清單結點入棧
       while(node != null){
           stack.push(node.val);
           node = node.next;
       }
       //棧中結點出棧建構新的單連結清單
       while(stack.pop() != null){
           prev.val = stack.pop();
           prev = prev.next;
       }
       return prev;
   }
              

四、單連結清單反轉（利用遞歸）也不咋地，不推薦，但是不太好了解，可以學習學習。

1. 基本思路：
   1. 連結清單的反轉關鍵就是讓指針域進行變更，
   2. 初始狀态：結點Null→A→B→C→Null 
   3. 需要調整為：結點Null←A←B←C←Null.
   4. 那麼我們用遞歸方法，就是讓在調整第一個連結清單的結點的指針域之前，先反轉後續結點。
   5. 層層深入，直至到尾結點為止才開始連結清單的反轉。
   6. 最後給出反轉後的單連結清單。
2. 具體實作（Java）:

   /*單連結清單的定義 Definition for singly-linked list*/
   public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
   }
   //利用遞歸反轉單連結清單
   public ListNode reverse(ListNode head){
       //判斷邊界情況
       if(head == null || head.next == null)
           return head;
       
       ListNode temp = head.next;//定義連結清單結點temp暫存目前節點（也就是第一個結點）的指針域。   
       
       ListNode newHead = reverse(head.next);  //對連結清單進行遞歸反轉。遞歸就展現在這裡 
       
       //這兩步屬于善後工作。
       temp.next = head;  //調整結點的指針域指向初始第一個結點。
       head.next = null;  //初始第一個結點指向null.
       
       return newHead;  //輸出反轉後的單連結清單。
   }
              

總結

以上，就是總結的内容。推薦使用第一種反轉連結清單，遞歸法可以多看看，有利于了解遞歸思想。