文章目錄
- 遞歸
- TestRecursiveListRemoveNode
- TestRecursiveListRemoveNode2
- 循環
- TestWhileLoopListRemoveNode
- TestWhileLoopListRemoveNode2
遞歸
關鍵理解這幾點:
1、求解基本問題
2、將原問題拆分為小問題,直至基本問題(難點)
3、借助設定的遞歸函數的語義,解決原問題
(在將原問題拆分成小問題時,可以借助設定的遞歸函數的語義,把設定的遞歸函數當作1個已實現的子函數,然后在遞歸函數中將原問題拆解成小問題,最終解決原問題)
TestRecursiveListRemoveNode
遞歸的技巧就是:你得先定義這個遞歸方法的目標功能
,然后在遞歸的實現方法中可以使用這個遞歸方法
,接著組織自己的邏輯,接著找出邊界條件
,還需要在遞歸方法實現中調用定義的遞歸方法,來驅動下一步的執行
!!!
- 實現功能:使用 遞歸的方式 刪除單向鏈表中指定值的節點
- 以遞歸的方式將單向鏈表內容,使用字符串的形式輸出
/*** 刪除單向鏈表中指定值的節點*/
public class TestRecursiveListRemoveNode {/*** 單向鏈表節點*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 組織鏈表結構// 這里不循環到list.size(),可以減少判斷for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 2種輸出指定頭節點的鏈表的方法// 方法1:把結果值傳入,然后不斷遞歸(遞歸方法無返回值)// 方法2:把控遞歸方法的含義,在遞歸方法中處理邊界,并使用已定義的遞歸方法(遞歸方法有返回值)System.out.println(printAllList1(listNode0));System.out.println(printAllList2(listNode0));// 遞歸的缺陷:當元素越多的情況下,方法調用棧的深度就深,甚至棧內存溢出ListNode listNode = removeElement(listNode1, 6); // (遞歸方法有返回值)System.out.println(printAllList1(listNode));System.out.println(printAllList2(listNode));/*輸出:6->6->1->2->6->3->4->6->5->6->6->76->6->1->2->6->3->4->6->5->6->6->71->2->3->4->5->71->2->3->4->5->7*/}// 遞歸的技巧就是:你得先定義這個遞歸方法的目標功能,然后在遞歸的實現方法中可以使用這個遞歸方法,// 接著組織自己的邏輯,接著找出邊界條件,還需要在遞歸方法實現中調用定義的遞歸方法,來驅動下一步的執行!!!// 先定義當前這個方法的目標功能就是:傳入1個鏈表的頭節點,返回1個鏈表的頭節點,并且這個鏈表頭節點的后續節點中都不包含指定的值private static ListNode removeElement(ListNode head, int val) {// (遞歸的技巧就是:在實現遞歸的時候,遞歸方法的下面都是要假設傳入的head有可能是第一次傳入的,也有可能是后面的遞歸調用傳入的,要有這個意識!!!)// 如果head是null, 則直接返回,因為沒有處理的必要了if (head == null) {return null;}// 如果頭節點的值就是指定的值,那么去除掉這個頭節點,把頭節點的下一個節點作為新的頭節點,// 將新的頭節點傳入給定義的遞歸方法,根據定義的遞歸方法本來含義,其實只要把新的頭節點傳給這個遞歸方法就解決了if (head.val == val) {ListNode next = head.next;return removeElement(next, val);}// 至此,說明head頭節點不是指定的值// 拿到頭節點的下1個節點ListNode next = head.next;// 如果頭節點的下1個節點不是空節點if (next != null) {// 如果頭節點的下1個節點的值就是目標值,那就讓頭節點指向下1個節點的下1個節點,// 不過在這里,頭節點的下1個節點的下1個節點,仍然需要經過遞歸方法的處理,所以這里又調用了一遍if (next.val == val) {head.next = removeElement(next.next, val);next.next = null;} else {// 如果頭節點的下1個節點的值不是目標值,那就繼續調用遞歸方法正常處理頭節點的下1個節點的下1個節點next.next = removeElement(next.next, val);}}// 如果頭節點的下1個節點就是空節點,那就直接返回頭節點就行了// 如果頭節點的下1個節點不是空節點,那經過上面的處理后,這里也直接返回頭節點就行了return head;}private static String printAllList2(ListNode head) {// 如果頭節點是空的,那就返回空字符串if (head == null) {return "";}// 傳過來的頭節點必定不為空// 拿到頭節點的下1個節點ListNode next = head.next;// 如果頭節點的下1個節點為空,那就直接返回這個頭節點了if (next == null) {return String.valueOf(head.val);} else {// 如果頭節點的下1個節點不為空,那就需要拼接上后面節點對應的結果了,由于當前遞歸方法的定義就是輸出指定節點的鏈表,所以這里直接調用遞歸的方法了!return head.val + "->" + printAllList2(next);}}private static String printAllList1(ListNode listNode) {// 先構造結果StringBuilder sb = new StringBuilder();// 遞歸處理結果(此處,遞歸方法無返回值)printAllList1(listNode, sb, 0);// 遞歸處理完成后,返回結果return sb.toString();}// 該遞歸方法定義是:根據傳入的指定節點,將這個節點及這個節點之后的所有節點都處理到sb上,形成 ->{節點值} 的形式private static void printAllList1(ListNode listNode, StringBuilder sb, int count) {// (遞歸的技巧就是:在實現遞歸的時候,遞歸方法的下面都是要假設傳入的head有可能是第一次傳入的,也有可能是后面的遞歸調用傳入的,要有這個意識!!!)// 傳入的節點為空,則不需要處理if (listNode == null) {return;}// 當count為0時,是第一次進入,因此前面不需要->if (count != 0) {sb.append("->");}// 標識是否第一次進入遞歸方法count++;// 將值設置的sb上sb.append(listNode.val);// 如果listNode還有下1個節點, 則繼續處理下1個節點,// 由于我們已經定義的遞歸方法,正好就是將 這個節點及這個節點之后的所有節點都處理到sb上,形成 ->{節點值} 的形式,// 因此這里又調用了遞歸方法if (listNode.next != null) {printAllList1(listNode.next, sb, count);}}}
TestRecursiveListRemoveNode2
比上面更簡潔。
關鍵理解這幾點:
1、求解基本問題
2、將原問題拆分為小問題,直至基本問題(難點)
3、借助設定的遞歸函數的語義,解決原問題
public class TestRecursiveListRemoveNode2{/*** 單向鏈表節點*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = getListNode();System.out.println(printAllList(listNode0));ListNode handledListNode = removeElements(listNode0, 6);System.out.println(printAllList(handledListNode));}public static ListNode removeElements(ListNode head, int val) {if (head != null) {if (head.val == val) {// 由于頭節點是給定的值,所以拋棄頭節點,此時,這里,借助 定義的遞歸函數的宏觀語義,只需要處理head.next即可返回return removeElements(head.next, val);} else {// 由于頭節點不是給定的值,所以對頭節點的下1個節點處理,此時,這里 借助定義的遞歸函數的宏觀語義,只需要處理head.next即可返回head.next = removeElements(head.next, val);return head;}}return null;/*// 與上面相同, 但這里更能體現出,在解決原問題的時候,是如何借助設定的遞歸方法,將原問題拆分成基礎問題的if (head == null) {return null;}ListNode res = removeElements(head.next, val);if (head.val == val) {return res;} else {head.next = res;return head;}*//*// 這整的有點高級了,意思和上面是相同的if (head == null) {return null;}head.next = removeElements(head.next, val);return head.val == val ? head.next : head;*/}private static String printAllList(ListNode head) {// 如果頭節點是空的,那就返回空字符串if (head == null) {return "";}// 傳過來的頭節點必定不為空// 拿到頭節點的下1個節點ListNode next = head.next;// 如果頭節點的下1個節點為空,那就直接返回這個頭節點了if (next == null) {return String.valueOf(head.val);} else {// 如果頭節點的下1個節點不為空,那就需要拼接上后面節點對應的結果了,由于當前遞歸方法的定義就是輸出指定節點的鏈表,所以這里直接調用遞歸的方法了!return head.val + "->" + printAllList(next);}}private static ListNode getListNode() {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 組織鏈表結構// 這里不循環到list.size(),可以減少判斷for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}return listNode0;}}
循環
TestWhileLoopListRemoveNode
- 實現功能:使用 循環的方式 刪除單向鏈表中指定值的節點
- 以循環的方式將單向鏈表內容,使用字符串的形式輸出
/*** 刪除單向鏈表中指定值的節點*/
public class TestWhileLoopListRemoveNode {/*** 單向鏈表節點*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 組織鏈表結構// 這里不循環到list.size(),可以減少判斷for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 使用循環(規避了遞歸可能引起的棧內存溢出的問題)System.out.println(printAllList(listNode0));// 使用循環(規避了遞歸可能引起的棧內存溢出的問題)ListNode node = removeElements(listNode0, 6);System.out.println(printAllList(node));}private static ListNode removeElements(ListNode head, int val) {// 去除可能存在的相連多個指定值的頭節點while (head != null && head.val == val) {ListNode next = head.next;head.next = null;head = next; // head向后推移1位,繼續循環}if (head == null) {return null;}// 將head值保存到prev,以開啟循環處理(循環處理的技巧)ListNode prev = head;while (prev.next != null) {// 拿到prev的下1個節點 nextListNode next = prev.next;if (next.val == val) { // 此處可借助循環移除多個連續相連的指定值的節點prev.next = next.next; // prev指向的下1個節點時,跳過指定值的節點,而指向下1個節點next.next = null;// 此處也繼續循環(并且注意此時prev值未變,繼續處理prev的下1個節點)} else {// 當prev的next不為指定值的節點時,prev向后推移1位,以繼續循環prev = prev.next;}}return head;}private static String printAllList(ListNode head) {if (head == null) {return "";}StringBuilder sb = new StringBuilder();sb.append(head.val);// 將head值保存到prev,以開啟循環處理(循環處理的技巧)ListNode prev = head;while (prev.next != null) {sb.append("->" + prev.next.val);prev = prev.next;}return sb.toString();}}
TestWhileLoopListRemoveNode2
- 實現功能:使用 循環的方式 刪除單向鏈表中指定值的節點(添加虛擬頭節點,統一化操作(簡化代碼))
- 以循環的方式將單向鏈表內容,使用字符串的形式輸出
/*** 刪除單向鏈表中指定值的節點(添加虛擬頭節點)*/
public class TestWhileLoopListRemoveNode2 {/*** 單向鏈表節點*/static class ListNode {private Integer val;private ListNode next;public ListNode(Integer val) {this.val = val;}@Overridepublic String toString() {return "ListNode="+ String.valueOf(val);}}public static void main(String[] args) {ListNode listNode0 = new ListNode(6);ListNode listNode0_1 = new ListNode(6);ListNode listNode1 = new ListNode(1);ListNode listNode2 = new ListNode(2);ListNode listNode2_1 = new ListNode(6);ListNode listNode3 = new ListNode(3);ListNode listNode4 = new ListNode(4);ListNode listNode4_1 = new ListNode(6);ListNode listNode5 = new ListNode(5);ListNode listNode6 = new ListNode(6);ListNode listNode7 = new ListNode(6);ListNode listNode8 = new ListNode(7);List<ListNode> list = new ArrayList<ListNode>(){{add(listNode0);add(listNode0_1);add(listNode1);add(listNode2);add(listNode2_1);add(listNode3);add(listNode4);add(listNode4_1);add(listNode5);add(listNode6);add(listNode7);add(listNode8);}};// 組織鏈表結構// 這里不循環到list.size(),可以減少判斷for (int i = 0; i < list.size() - 1; i++) {list.get(i).next = list.get(i + 1);}// 使用循環(規避了遞歸可能引起的棧內存溢出的問題)System.out.println(printAllList(listNode0));// 使用循環(規避了遞歸可能引起的棧內存溢出的問題)// (添加虛擬頭節點技巧)ListNode node = removeElements(listNode0, 6);System.out.println(printAllList(node));}private static ListNode removeElements(ListNode head, int val) {// 添加1個虛擬頭節點,來去除對head為空的情況的判斷,從而簡化代碼ListNode dummyNode = new ListNode(null);dummyNode.next = head;// 將head值保存到prev,以開啟循環處理(循環處理的技巧)ListNode prev = dummyNode;while (prev.next != null) {// 拿到prev的下1個節點 nextListNode next = prev.next;if (next.val == val) { // 此處可借助循環移除多個連續相連的指定值的節點prev.next = next.next; // 跳過指定值的節點next.next = null;// 此處也繼續循環(并且注意此時prev值未變)} else {// 當prev的next不為指定值的節點時,prev向后推移1位,以繼續循環prev = prev.next;}}// 返回時,也是返回虛擬頭節點的下一個節點return dummyNode.next;}private static String printAllList(ListNode head) {if (head == null) {return "";}StringBuilder sb = new StringBuilder();sb.append(head.val);ListNode prev = head;while (prev.next != null) {sb.append("->" + prev.next.val);prev = prev.next;}return sb.toString();}}