文章目录
递归
关键理解这几点：
1、求解基本问题
2、将原问题拆分为小问题，直至基本问题（难点）
3、借助设定的递归函数的语义，解决原问题
（在将原问题拆分成小问题时，可以借助设定的递归函数的语义，把设定的递归函数当作1个已实现的子函数，然后在递归函数中将原问题拆解成小问题，最终解决原问题）
TestRecursiveListRemoveNode
递归的技巧就是：你得先定义这个递归方法的目标功能，然后在递归的实现方法中可以使用这个递归方法，接着组织自己的逻辑，接着找出边界条件，还需要在递归方法实现中调用定义的递归方法，来驱动下一步的执行!!!
- 实现功能：使用 递归的方式 删除单向链表中指定值的节点
- 以递归的方式将单向链表内容，使用字符串的形式输出
/**
* 删除单向链表中指定值的节点
*/
public class TestRecursiveListRemoveNode {
/**
* 单向链表节点
*/
static class ListNode {
private Integer val;
private ListNode next;
public ListNode(Integer val) {
this.val = val;
}
@Override
public 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->7
6->6->1->2->6->3->4->6->5->6->6->7
1->2->3->4->5->7
1->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;
}
@Override
public 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;
}
@Override
public 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个节点 next
ListNode 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;
}
@Override
public 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个节点 next
ListNode 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();
}
}