單雙鏈表及其反轉——堆棧詮釋

按值傳遞

• int、long、byte、short、char、float、double、boolean和String 都是按值傳遞

• 概念：在方法被調用時，實參通過形參把它的內容副本傳入方法內部，此時形參接收到的內容是實參值的一個拷貝，因此在方法內對形參的任何操作，都僅僅是對這個副本的操作，不影響原始值的內容

• 分析：向函數傳參時，只是在棧中生成變量a的一個副本a1，在函數內被修改的a其實是a1，所以函數內修改參數的值并不會影響實參的值，這就是值傳遞

  int a = 10;
  f(a);
  system.out.println(a);public static void f(int a) {a = 0;
  }// 結果還是打印10
  

按引用傳遞

• 其他類型和數值都是按引用傳遞

• 概念：”引用”也就是指向真實內容的地址值，在方法調用時，實參的地址通過方法調用被傳遞給相應的形參，在方法體內，形參和實參指向通愉快內存地址，對形參的操作會影響的真實內容

• 分析：

  • 創建Number對象存儲在堆中，并將其引用地址賦值給變量b
  • 調用g1()和g2()方法時，棧空間中會拷貝對象引用地址為b1和b2并作為參數傳遞，因此b、b1和b2都指向堆中同一個Number對象
  • 在g1()方法中，將參數b1修改為null，這只是改變了b1的指向，不影響主函數中變量b的指向，主函數的b仍然指向原來的Number對象。
  • 在g2()方法中，通過參數b2修改b2.val的值為6，這相當于通過b2的引用地址找到并修改了堆中Number對象的val值，因此主函數中變量b所指向的Number對象的val值也會被修改
  • 總結：指向的是同一個內存區域，但是不同的兩個引用

  public static void main(String[] args){Number b = new Number(5);g1(b);System.out.println(b.val);g2(b);System.out.println(b.val);
  }
  // 結果：
  // 5
  // 6public static class Number{public int val;public Number(int v){val = v;}
  }public static void g1(Number b){b = null;
  }public static void g3(Number b){b.val = 6;
  }public static void g3(int[] c){c = null;
  }
  

單鏈表的定義

• 什么是單鏈表，單鏈表是一種通過指針串聯在一起的線性結構，每一個節點由兩部分組成，一個是數據域一個是指針域（存放指向下一個節點的指針），最后一個節點的指針域指向null
• 單鏈表不要求邏輯上相鄰的兩個元素在物理位置上也相鄰，因此不需要連續的存儲空間
• 單鏈表的入口節點稱為鏈表的頭結點也就是head

public class ListNode {// 結點的值public int val;// 下一個節點public ListNode next;// 節點的構造函數(有兩個參數)public ListNode(int val, ListNode next) {this.val = val;this.next = next;}
}

雙鏈表的定義

• 什么是雙鏈表，雙鏈表是一種通過指針串聯在一起的線性結構，每一個節點由三部分組成，每個節點包含數據域、指向下一個節點的指針（next）和指向前一個節點的指針（prev）
• 雙鏈表 既可以向前查詢也可以向后查詢
• 雙鏈表的入口節點稱為鏈表的頭結點也就是head

public class DoubleListNode {// 結點的值public int val;// 下一個節點public DoubleListNode next;// 上一個節點public DoubleListNode prev;// 節點的構造函數(有兩個參數)public ListNode(int val, DoubleListNode next) {this.val = val;this.prev = prev;this.next = next;}
}

反轉單鏈表

public static ListNode reverseList(ListNode head){ListNode pre = null;ListNode next = null;while (head != null){next = head.next;head.next = pre;pre = head;head = next;}return pre;
}

反轉雙鏈表

public static ListNode reverseDoubleList(DoubleListNode head){DoubleListNode pre = null;DoubleListNode next = null;while (head != null){next = head.next;head.next = pre;head.last = next;pre = head;head = next;}return pre;
}