玩转数据结构——第四章：链表和递归
内容概要：
- Leetcode中和链表相关的问题
- 测试自己的Leetcode链表代码
- 递归继承与递归的宏观语意
- 链表的天然递归结构性质
- 递归运行机制：递归的微观解读
- 递归算法的调试
- 更多和链表相关的问题
1-Leetcode中和链表相关的问题
题目：
删除链表中等于给定的val的所有元素。
示例：
给定：1—>2—>6—>3—>4—>5—>6,val=6
返回：1—>2—>3—>4—>5
给定的ListNode类
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
}问题分析：
- 第一种解决方案：链表没有设置虚拟头结点
首先，判断链表是否为空(head!=null)为空则返回head，不为空执行下面删除操作
处理特殊位置，链表头部的删除工作：如果head是val值(head.val=val)
ListNode delNode=head;
head=head.next;
delNode.next=null;然后删除中间位置的方法：
定义prev为要删除节点的前一个节点
ListNode prev=head;
prev.next下一个节点不为空则且prve.next.val==val则执行删除操作
ListNode delNode=prev.next;//定义要删除的节点
prev.next=delNode.next;
delNode.next=null;否则，prev=prev.next;继续往下找
class Solution {
public ListNode removeElements(ListNode head, int val) {
//1假设head节点的val等于给定的val
//1解决头结点的删除
while (head != null && head.val == val) {
//定义要删除的那个节点
ListNode delNode = head;
head = head.next;
delNode.next = null;
}
//如果头结点为空
if (head == null)
return null;
//2解决中间部分的删
ListNode prev = head;//头结点为下一个节点的前一个节点
while (prev.next != null) {//下一个节点不为空
if (prev.val == val) {///中间部分的某一个节点的val等于给定val
ListNode delNode = prev.next;
prev.next = delNode.next;
delNode.next = null;
} else {//prev往下找
prev = prev.next;
}
}
return head;
}
}- 第二种解决方案：链表设置虚拟头结点
在链表的头部设置一个虚拟头结点，则除了头部删除和中间删除都是同一个操作
class Solution2 {
public ListNode removeElements(ListNode head, int val) {
ListNode dummyhead = new ListNode(-1);//设置虚拟节点，值任意
dummyhead.next = head;//虚拟节点成头结点
//解决头结点和中间部分的删
ListNode prev = dummyhead;//头结点为下一个节点的前一个节点
while (prev.next != null) {//下一个节点不为空
if (prev.next.val == val) {///中间部分的某一个节点的val等于给定val
// ListNode delNode = prev.next;
// prev.next = delNode.next;
// delNode.next = null;
prev.next = prev.next.next;//和上面三句等效
} else {//prev往下找
prev = prev.next;
}
}
return dummyhead.next;//虚拟头结点不展示
}}2-测试自己的Leetcode链表代码
在给定的ListNode类中，写一个带参构造函数，参数传进来一个整形数组，转成链表
public class ListNode {
public int val;
public ListNode next;
public ListNode(int x) {
val = x;
}
//链表节点的构造函数
//使用arr为参数。创建一个链表。当前的ListNode为链表的头结点
public ListNode(int[] arr) {
if (arr == null || arr.length == 0)
throw new IllegalArgumentException("arr cannot be empt");
this.val = arr[0];
ListNode cur = this;//this用来保存cur的状态 //里面记录的所以cur的状态1->NUll /1->2->NULL/1->2->3-NULL....
for (int i = 1; i < arr.length; i++) {
cur.next = new ListNode(arr[i]);//每次传入新的参数生成新的对象，赋值给cur.next
cur = cur.next;//将cur.next传给cur作为新的cur的位置，传递
}
}
@Override
public String toString() {
StringBuilder res = new StringBuilder();
ListNode cur = this;//this通过上面的方法村里
while (cur != null)
{
res.append(cur.val + "->");
cur = cur.next;
}
res.append("NULL");
return res.toString();
}
}在Solution中实现测试
public static void main (String[] args){
int[] nums={1,2,3,6,4,5,6};
//利用带参构造函数将数组变成新的链表
ListNode node=new ListNode(nums);
System.out.println(node);
ListNode newNode=new Solution().removeElements(node,6);
System.out.println(newNode);
}结果：
1->2->3->6->4->5->6->NULL
1->2->3->4->5->NULL3-递归继承与递归的宏观语意
递归：本质上,将原来的问题，转化为更小的同一问题
/**
* 采用递归的方式来计算数组的和
*/
public class Sum {
public static int sum(int[] arr) {
return sum(arr, 0);//递归的调用，从0到n-1的和
}
//真正的递归
//计算arr[l,n)这个区间内所有数字的和
protected static int sum(int[] arr, int l) {
if (l == arr.length)
return 0;
//解决的问题规模变小了一层一层的调用(计算【l+1,n)的和...计算[n-1,n)的和)
return arr[l] + sum(arr, l + 1);
}}测试函数： 结果36
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
System.out.println(sum(arr));
}
4-链表的天然递归结构性质
用递归算法的两个步骤：
- 1.先求解最基本问题
- 2.把原问题转化成更小的问题
用递归的算法解决删除链表元素中为e的值
/**
* 使用递归解决删除链表中为e的元素
*/
class Solution2 {
public ListNode removeElements(ListNode head, int val) {
//第一步：解决最基本的问题
if (head == null)
return null;
head.next = removeElements(head.next, val);
return head.val == val ? head.next : head;
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 6, 4, 5, 6};
//利用带参构造函数将数组变成新的链表
ListNode node = new ListNode(nums);
System.out.println(node);
ListNode newNode = new Solution2().removeElements(node, 6);
System.out.println(newNode);
}
}5-递归运行机制：递归的微观解读
如果不解决函数的基本问题(最后那一层，head==null)，递归将永远进行下去，直到占满系统栈的空间。
6-递归算法的调试
使用打印输出的方式来理解从链表移除val元素的值的运行过程
/**
* 使用打印输出的方式来输出链表移除元素val的值的运行过程
*/
class Solution2 {
public ListNode removeElements(ListNode head, int val, int depth) {
String depthString = generateDepthString(depth);
System.out.print(depthString);
System.out.println("Call:remove " + val + " in " + head);
//第一步：解决最基本的问题
if (head == null) {
System.out.print(depthString);
System.out.println("Return:remove " + head);
return null;
}
ListNode res = removeElements(head.next, val, depth + 1);
System.out.print(depthString);
System.out.println("After:remove " + val + " in " + res);
ListNode ret;//暂存
if (head.val == val)
ret = res;
else
head.next = res;
ret = head;
System.out.print(depthString);
System.out.println("Return: " + ret);
return ret;
}
private String generateDepthString(int depth) {
StringBuilder res = new StringBuilder();
for (int i = 0; i < depth; i++) {
res.append("-|");
}
return res.toString();
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 6, 4, 5, 6};
//利用带参构造函数将数组变成新的链表
ListNode node = new ListNode(nums);
System.out.println(node);
ListNode newNode = new Solution2().removeElements(node, 6, 0);
System.out.println(newNode);
}
}输出结果：
1->2->3->6->4->5->6->NULL
Call:remove 6 in 1->2->3->6->4->5->6->NULL
-|Call:remove 6 in 2->3->6->4->5->6->NULL
-|-|Call:remove 6 in 3->6->4->5->6->NULL
-|-|-|Call:remove 6 in 6->4->5->6->NULL
-|-|-|-|Call:remove 6 in 4->5->6->NULL
-|-|-|-|-|Call:remove 6 in 5->6->NULL
-|-|-|-|-|-|Call:remove 6 in 6->NULL
-|-|-|-|-|-|-|Call:remove 6 in null
-|-|-|-|-|-|-|Return:remove null
-|-|-|-|-|-|After:remove 6 in null
-|-|-|-|-|-|Return: 6->NULL
-|-|-|-|-|After:remove 6 in 6->NULL
-|-|-|-|-|Return: 5->6->NULL
-|-|-|-|After:remove 6 in 5->6->NULL
-|-|-|-|Return: 4->5->6->NULL
-|-|-|After:remove 6 in 4->5->6->NULL
-|-|-|Return: 6->4->5->6->NULL
-|-|After:remove 6 in 6->4->5->6->NULL
-|-|Return: 3->6->4->5->6->NULL
-|After:remove 6 in 3->6->4->5->6->NULL
-|Return: 2->3->6->4->5->6->NULL
After:remove 6 in 2->3->6->4->5->6->NULL
Return: 1->2->3->6->4->5->6->NULL
1->2->3->6->4->5->6->NULL7-更多和链表相关的问题