劍指 Offer 06.從尾到頭列印連結串列
思考：利用棧“先進後出”的性質。遍歷連結串列，儲存結點值。遍歷輸出棧值。業務程式碼還是很容易寫的。
引申可見 劍指 Offer 24 .反轉連結串列
為了在IDEA上方便除錯，需要實現“nums2ListNode”，即陣列轉連結串列的業務程式碼。
自己寫的程式的規格結構。
private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; }為了在IDEA上方便除錯，需要實現“printListNode”，即連結串列內容列印的業務程式碼。
private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); }完整程式碼：
ArrayList<Integer>如何轉換為int[]陣列 https://blog.csdn.net/huanghanqian/article/details/73920439 這個是java8的特性 int[] res = list.stream().mapToInt(Integer::intValue).toArray();
import java.util.ArrayList; import java.util.LinkedList; import java.util.Stack; public class Offer06 { public static void main(String[] args) { int[] nums = new int[]{1, 3, 2}; ListNode head = nums2ListNode(nums); printListNode(head); System.out.println(reversePrint(head)); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static int[] reversePrint(ListNode head) { Stack<Integer> stack = new Stack<>(); ArrayList<Integer> list = new ArrayList<>(); while (head != null) { stack.push(head.val); head = head.next; } while (!stack.isEmpty()) { list.add(stack.pop()); } // ArrayList<Integer>如何轉換為int[]陣列 https://blog.csdn.net/huanghanqian/article/details/73920439 // 這個是java8的特性 int[] res = list.stream().mapToInt(Integer::intValue).toArray(); return res; } } ListNode的程式碼放在外邊
public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }思考：這個考慮可能刪除頭結點，尾節點，等情況，需要採用“虛擬頭結點”+“快慢指標”的操作。
import java.util.ArrayList; import java.util.Stack; public class Offer18 { public static void main(String[] args) { int[] nums = new int[]{4, 5, 1, 9}; ListNode head = nums2ListNode(nums); printListNode(head); ListNode resHead = deleteNode(head, 5); printListNode(resHead); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static ListNode deleteNode(ListNode head, int val) { // 1.建立虛擬頭結點 ListNode dummyNode = new ListNode(0); dummyNode.next = head; // 2.建立快慢指標 ListNode fast = dummyNode.next; ListNode slow = dummyNode; // 3.遍歷查詢需要刪除的節點 while (fast != null) { // 一個要刪除的節點的值 if (fast.val == val) { // 該節點的前一個節點指向該節點的後一個節點 slow.next = fast.next; // 將該節點的next指向null。這裡好像是加不加都可以。 fast.next = null; break; } // 更新節點 slow = slow.next; fast = fast.next; } // 這裡是考慮到頭結點就是要刪除的節點的情況 return dummyNode.next; } }思考：“快慢指標”，先讓快指標走k步，然後快慢指標同時向前走，當快指標到達連結串列末尾，慢指標指向了目標節點。
public class Offer22 { public static void main(String[] args) { int[] nums = new int[]{1, 2, 3, 4, 5}; ListNode head = nums2ListNode(nums); printListNode(head); ListNode resHead = getKthFromEnd(head, 2); printListNode(resHead); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static ListNode getKthFromEnd(ListNode head, int k) { // 1.建立快慢指標 ListNode fast = head; ListNode slow = head; // 2.先讓快指標走k步 for (int i = 0; i < k; i++) { fast = fast.next; } // 3.然後快慢指標同時向前走，當快指標到達連結串列末尾，慢指標指向了目標節點。 while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } }思考：“雙指標”，1.儲存cur的下一個節點。2.轉向，後節點指向前節點。3.更新節點，兩個節點都向前走一步。這個做題步驟特別統一。不能採用“虛擬頭結點”，pre應該直接設定為null。
public class Offer24 { public static void main(String[] args) { int[] nums = new int[]{1, 2, 3, 4, 5}; ListNode head = nums2ListNode(nums); printListNode(head); ListNode resHead = reverseList(head); printListNode(resHead); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static ListNode reverseList(ListNode head) { // 1.建立雙指標 ListNode pre = null; ListNode cur = head; while (cur != null) { // 2.儲存cur的下一個節點 ListNode nextNode = cur.next; // 3.轉向，後節點指向前節點。 cur.next = pre; // 4.更新節點，兩個節點都向前走一步。 pre = cur; cur = nextNode; } // 經過while,cur指向為null，pre指向尾節點。 return pre; } }思考：新建一個連結串列，比較連結串列l1和l2的值，依次將元素新增到新連結串列中。
【力扣官方將這個題目歸為了分治演算法】
先去寫 newNode = newNode.next;是不行的，newNode.next現在是null，必須先去newNode.next=l1，這樣給newNode.next賦值，才能更新newNode節點：newNode = newNode.next;
public class Offer25 { public static void main(String[] args) { int[] nums1 = new int[]{1, 2, 4}; int[] nums2 = new int[]{1, 3, 4}; ListNode l1 = nums2ListNode(nums1); ListNode l2 = nums2ListNode(nums2); printListNode(l1); printListNode(l2); ListNode resHead = mergeTwoLists(l1, l2); printListNode(resHead); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode dummyNode = new ListNode(0); ListNode newNode = dummyNode; // 迴圈結束條件 && 使得l1,l2其中一個為空時，則跳出while迴圈。 while (l1 != null && l2 != null) { // 獲取l1,l2中較小的節點，新增到新連結串列 newNode 中。 if (l1.val < l2.val) { newNode.next = l1; // 更新連結串列 l1 l1 = l1.next; } else { newNode.next = l2; // 更新連結串列 l2 l2 = l2.next; } // 更新新連結串列 newNode newNode = newNode.next; } // l1,l2其中一個為空。 newNode.next = l1 != null ? l1 : l2; return dummyNode.next; } }思考：這個題目難度明顯比前面的幾道題目要難一點。程式碼參考自1：+程式碼參考自2，java版本：
首先，先新建一個Node類
public class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } }測試用例：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]。明顯，自己不能用IDEA去建立測試用例。
1.雜湊表方法，影片講解如下：bilibili影片講解：小美圖解：java版 小美圖解劍指offer35題 複雜連結串列的複製 演算法刷題。這個影片多看幾次，加深理解。
首先利用 HashMap 來一個不用思考的程式碼。 遍歷第一遍連結串列，我們不考慮連結串列之間的相互關係，僅僅生成所有節點，然後把它存到 HashMap 中，val 作為 key，Node 作為 value。 遍歷第二遍連結串列，將之前生成的節點取出來，更新它們的 next 和 random 指標。
import java.util.HashMap; public class Offer35 { public static void main(String[] args) { System.out.println(" 測試用例：`head = [[7,null],[13,0],[11,4],[10,2],[1,0]]`。"); System.out.println("明顯，自己不能用IDEA去建立測試用例。"); } public Node copyRandomList(Node head) { // 給定的連結串列為空（空指標），因此返回 null。 if (head == null) { return null; } // 新建 HashMap 遍歷儲存 連結串列的節點+節點值。 // 鍵值對都是Node型別。 HashMap<Node, Node> map = new HashMap<>(); Node cur = head; // 複製各節點，並建立 “原節點 -> 新節點” 的 Map 對映 while (cur != null) { Node val = new Node(cur.val); map.put(cur, val); cur = cur.next; } // 遍歷完成後返回到頭結點 cur = head; // 構建新連結串列的 next 和 random 指向 while (cur != null) { if (cur.next != null) { map.get(cur).next = map.get(cur.next); } if (cur.random != null) { map.get(cur).random = map.get(cur.random); } cur = cur.next; } // 返回新連結串列的頭節點 return map.get(head); } }2.bilibili影片講解【採用了遞迴的方法。可以先不看這個解法。感覺看了下面的程式碼，更加困惑了。】來自 子爍愛學習
import java.util.HashMap; public class Offer35_bilibili { public static void main(String[] args) { System.out.println(" 測試用例：`head = [[7,null],[13,0],[11,4],[10,2],[1,0]]`。"); System.out.println("明顯，自己不能用IDEA去建立測試用例。"); } HashMap<Node, Node> map = new HashMap<>(); public Node copyRandomList(Node head) { if (head == null) { return null; } if (map.containsKey(head)) { return map.get(head); } Node tempNode = new Node(head.val); map.put(head, tempNode); // 這裡有一個遞迴呼叫哦。 tempNode.next = copyRandomList(head.next); // 這裡有一個遞迴呼叫哦。上面的遞迴完成，這裡才會執行。 tempNode.random = copyRandomList(head.random); return tempNode; } } 思考：一種方法是：用A的一個節點，去比較B的所有節點。複雜度是O(n^2)。
public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode copyheadB=headB; while(headA!=null){ while(headB!=null){ if(headA==headB){ return headA; }else{ headB=headB.next; } } headA=headA.next; headB=copyheadB; } return null; } }思考：另一個巧妙的思路是：我們使用兩個指標 node1，node2 分別指向兩個連結串列 headA，headB 的頭結點，然後同時分別逐結點遍歷，當 node1 到達連結串列 headA 的末尾時，重新定位到連結串列 headB 的頭結點；當 node2 到達連結串列 headB 的末尾時，重新定位到連結串列 headA 的頭結點。這樣，當它們相遇時，所指向的結點就是第一個公共結點。
假如兩個沒有交點，兩個連結串列一直交換不會死迴圈嗎？
答：如果沒有重合部分，那麼 a 和 b 在某一時間點 一定會同時走到 null，從而結束迴圈。System.out.println(null==null);// 輸出為 true while (PA != PB) 在這裡會跳出while迴圈，到達下一步 return PA，也就是 return null。
如果有重合部分，分兩種情況。
長度相同的話， a 和 b 一定是同時到達相遇點，然後返回。 長度不同的話，較短的連結串列先到達結尾，然後指標轉向較長的連結串列。此刻，較長的連結串列繼續向末尾走，多走的距離剛好就是最開始介紹的解法，連結串列的長度差，走完之後指標轉向較短的連結串列。然後繼續走的話，相遇的位置就剛好是相遇點了。
影片講解：小美圖解劍指Offer 52題 兩個連結串列的第一個公共節點 java版本
headA：4->1->8->4->5 headB：5->0->1->8->4->5
headAB：4->1->8->4->5->5->0->1->8->4->5
headBA：5->0->1->8->4->5->4->1->8->4->5
測試用例如上圖，但是我在IDEA上不會設定測試用例，最終程式碼如下。程式碼參考自1：+程式碼參考自2：
public class Offer52 { public static void main(String[] args) { int[] nums1 = new int[]{4, 1, 8, 4, 5}; int[] nums2 = new int[]{5, 0, 1, 8, 4, 5}; ListNode headA = nums2ListNode(nums1); ListNode headB = nums2ListNode(nums2); printListNode(headA); printListNode(headB); ListNode resHead = getIntersectionNode(headA, headB); printListNode(resHead); } private static void printListNode(ListNode head) { StringBuffer res = new StringBuffer(); while (head.next != null) { res.append(head.val + "->"); head = head.next; } res.append(head.val); System.out.println(res); } private static ListNode nums2ListNode(int[] nums) { // 1.首先先去建立頭結點 ListNode head = new ListNode(nums[0]); // 2.建立結點 node 去遍歷陣列元素 ListNode node = head; // 3.從陣列的第2個元素依次遍歷 for (int i = 1; i < nums.length; i++) { // 4.建立臨時結點 ListNode temp = new ListNode(nums[i]); node.next = temp; // 更新 node 節點 node = temp; } return head; } public static ListNode getIntersectionNode(ListNode headA, ListNode headB) { ListNode PA = headA; ListNode PB = headB; while (PA != PB) { PA = (PA == null ? headB : PA.next); PB = (PB == null ? headA : PB.next); } return PA; } }
最新評論