本系列博客习题来自《算法(第四版)》，算是本人的读书笔记，如果有人在读这本书的，欢迎大家多多交流。为了方便讨论，本人新建了一个微信群(算法交流)，想要加入的，请添加我的微信号：zhujinhui207407 谢谢。另外，本人的个人博客 http://www.kyson.cn 也在不停的更新中，欢迎一起讨论
算法(第4版)
知识点
- 链表节点增删查改
题目
1.3.18 假设x是一条链表的某个结点且不是尾结点。下面这条语句的效果是什么？
1.3.18 Suppose x is a linked-list node and not the last node on the list.What is the effect of the following code fragment?
x.next = x.next.next;
Answer : Deletes from the list the node immediately following x.
分析
删除节点
答案
删除紧临在x后面的一个结点。
题目
1.3.19 给出一段代码，删除链表的尾结点，其中链表的首结点为first。
1.3.19 Give a code fragment that removes the last node in a linked list whose first node is first.
分析
要删除尾结点，需要找到倒数第二个结点。尾结点为node->next == null。将倒数第二个结点置为null即可。
答案
public class LinkedListExecise1<Item> {
// 节点
private static class Node<Item> {
Node<Item> next;
Item item;
}
public Node<Item> deleteLastNode(Node<Item> first) {
if (first == null) {
return null;
}
//current是当前遍历到的节点
Node<Item> current = first;
if (current.next == null) {
first = null;
return first;
}
//secondLast 倒数第二个节点
Node<Item> secondLast = first;
while (current.next != null) {
//这里是引用，操作secondLast就是操作链表本身
secondLast = current;
current = current.next;
}
//这里是引用，操作secondLast就是操作链表本身
secondLast.next = null;
return first;
}
public static void main(String[] args) {
/**
* 创建链表
* */
Node<String> first = new Node<String>();
Node<String> second = new Node<String>();
Node<String> third = new Node<String>();
Node<String> forth = new Node<String>();
Node<String> fifth = new Node<String>();
first.item = "我的";
first.next = second;
second.item = "名字";
second.next = third;
third.item = "叫";
third.next = forth;
forth.item = "顶级程序员不穿女装";
forth.next = fifth;
fifth.item = "微博:https://m.weibo.cn/p/1005056186766482";
fifth.next = null;
//删除尾节点之前
System.out.println("原链表：\n-------");
Node current1 = first;
while (current1.next != null) {
System.out.println(current1.item);
current1 = current1.next;
}
System.out.println(current1.item);
System.out.println("-------");
LinkedListExecise1<String> linkedListExercise1 = new LinkedListExecise1<String>();
//删除最后一个元素
System.out.println("正在删除链表最后一个节点...");
Node<String> resultNode = linkedListExercise1.deleteLastNode(first);
System.out.println("删除成功");
System.out.println("新链表：\n-------");
Node current2 = resultNode;
while (current2.next != null) {
System.out.println(current2.item);
current2 = current2.next;
}
System.out.println(current2.item);
System.out.println("-------");
}
}
代码索引
题目
1.3.20 编写一个方法delete()，接受一个int参数k，删除链表的第k个元素（如果它存在的话）。
1.3.20 Write a method delete() that takes an int argument k and deletes the kth element in a linked list, if it exists.
分析
分多种情况，当链表为空链表，当链表只有一个节点，当链表有多个节点
答案
public class LinkedListExecise2<Item> {
private static class Node<Item> {
Node next;
Item item;
}
/**
*
* @param k 第K个元素
* @param first 链表的首节点
* @return 新的链表
* @throws Exception
*/
public Node<Item> delete(int k, Node<Item> first) throws Exception{
if (k < 0 || first == null) return null;
if (k == 0) {
first = first.next;
return first;
}
Node<Item> current = first;
while (current != null && --k != 0) {
current = current.next;
}
if (k!= 0 || current.next == null || current == null) {
throw new Exception();
}else {
current.next = current.next.next;
}
return first;
}
public static void main(String[] args) {
/**
* 创建链表
* */
Node<String> first = new Node<String>();
Node<String> second = new Node<String>();
Node<String> third = new Node<String>();
Node<String> forth = new Node<String>();
Node<String> fifth = new Node<String>();
first.item = "我的";
first.next = second;
second.item = "名字";
second.next = third;
third.item = "叫";
third.next = forth;
forth.item = "顶级程序员不穿女装";
forth.next = fifth;
fifth.item = "微博:https://m.weibo.cn/p/1005056186766482";
fifth.next = null;
// 删除尾节点之前
System.out.println("原链表：\n-------");
Node current1 = first;
while (current1.next != null) {
System.out.println(current1.item);
current1 = current1.next;
}
System.out.println(current1.item);
System.out.println("-------");
LinkedListExecise2<String> linkedListExercise2 = new LinkedListExecise2<String>();
// 删除第一个元素
int k = 4;
System.out.println("正在删除链表第" + k + "个节点...");
Node<String> resultNode = null;
try {
resultNode = linkedListExercise2.delete(k,first);
} catch (Exception e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
System.out.println("删除成功");
System.out.println("新链表：\n-------");
Node current2 = resultNode;
while (current2.next != null) {
System.out.println(current2.item);
current2 = current2.next;
}
System.out.println(current2.item);
System.out.println("-------");
}
}
代码索引
视频讲解
广告
我的首款个人开发的APP壁纸宝贝上线了，欢迎大家下载。
