本系列博客習題來自《算法(第四版)》拾稳，算是本人的讀書筆記，如果有人在讀這本書的腊脱，歡迎大家多多交流访得。為了方便討論，本人新建了一個微信群(算法交流)陕凹，想要加入的悍抑，請?zhí)砑游业奈⑿盘枺簔hujinhui207407 謝謝。另外杜耙，本人的個人博客 http://www.kyson.cn 也在不停的更新中搜骡，歡迎一起討論
知識點
- 鏈表節(jié)點增刪查改
- 環(huán)形鏈表
題目
1.3.28 用遞歸的方法解答上一道練習
1.3.28 Develop a recursive solution to the previous question.
題目
1.3.29 用環(huán)形鏈表實現(xiàn)Queue。環(huán)形鏈表也是一條鏈表佑女，只是沒有任何結點鏈接為空记靡，且只要鏈表非空則last.next的值就為first。只能使用一個Node類型的實例變量（last）珊豹。
1.3.29 Write a Queue implementation that uses a circular linkedlist,which is the same as a linked list except that no links are null and the value of last.next is first when- ever the list is not empty. Keep only one Node instance variable (last).
答案
public class CircularLinkedListQueue<Item> implements Iterable<Item>{
private class Node<Item> {
Item item;
Node<Item> next;
}
private Node<Item> last;
private int N = 0;
public void enqueue(Item item) {
Node<Item> node = new Node<Item>();
node.item = item;
if (this.isEmpty()) {
node.next = node;
last = node;
N++;
}else {
node.next = last.next;
last.next = node;
last = node;
N++;
}
}
public Item dequeue() {
if (this.isEmpty()) {
return null;
}
Node<Item> first = last.next;
last.next = last.next.next;
N--;
return first.item;
}
public boolean isEmpty(){
return last == null;
}
public Iterator<Item> iterator() {
return new QueueIterator();
}
private class QueueIterator implements Iterator<Item>
{
Node<Item> current = last;
int index = 0;
public boolean hasNext() {
if (last == null) {
return false;
}
if (index < N) {
return true;
}
return false;
}
public Item next() {
current = current.next;
index++;
return current.item;
}
public void remove() {
}
}
public static void main(String[] args) {
CircularLinkedListQueue<String> queue = new CircularLinkedListQueue<String>();
queue.enqueue("我的");
queue.enqueue("名字");
queue.enqueue("叫");
queue.enqueue("頂級程序員不穿女裝");
queue.enqueue("微博:https://m.weibo.cn/p/1005056186766482");
queue.dequeue();
queue.dequeue();
for (String string : queue) {
System.out.println(string);
}
System.out.println(queue);
}
}
代碼索引
題目
1.3.30 編寫一個函數(shù)簸呈，接受一條鏈表的首結點作為參數(shù)，（破壞性地）將鏈表反轉并返回結果鏈表的首結點店茶。
1.3.30 Write a function that takes the first Node in a linked list as argument and (de- structively) reverses the list, returning the first Node in the result.
Iterative solution : To accomplish this task, we maintain references to three consecutive nodes in the linked list, reverse, first, and second. At each iteration, we extract the node first from the original linked list and insert it at the beginning of the reversed list. We maintain the invariant that first is the first node of what’s left of the original list, second is the second node of what’s left of the original list, and reverse is the first node of the resulting reversed list.
public Node reverse(Node x)
{
Node first = x;
Node reverse = null;
while (first != null)
{
Node second = first.next;
first.next = reverse;
reverse = first;
first = second;
}
return reverse;
}
When writing code involving linked lists, we must always be careful to properly handle the exceptional cases (when the linked list is empty, when the list has only one or two nodes) and the boundary cases (dealing with the first or last items). This is usually much trickier than handling the normal cases.
Recursive solution : Assuming the linked list has N nodes , we recursively reverse the last N – 1 nodes, and then carefully append the first node to the end.
public Node reverse(Node first)
{
if (first == null) return null;
if (first.next == null) return first;
Node second = first.next;
Node rest = reverse(second);
second.next = first;
first.next = null;
return rest;
}
答案
public class LinkedListExecise8<Item> {
private static class Node<Item> {
Node next;
Item item;
public String toString() {
return "item:" + item;
}
}
public static Node reverse(Node x){
Node first = x;
Node reverse = null;
while(first != null){
Node second = first.next;
first.next = reverse;
reverse = first;
first = second;
}
return reverse;
}
public static void main(String[] args) {
/**
* 創(chuàng)建鏈表
*/
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;
Node newFirst = reverse(first);
Node current = newFirst;
while (current != null) {
System.out.println(current.item);
current = current.next;
}
}
}
代碼索引
題目
1.3.31 實現(xiàn)一個嵌套類DoubleNode用來構造雙向鏈表蜕便，其中每個結點都含有一個指向前驅元素的引用和一個指向后續(xù)元素的引用（如果不存在則為null）。為以下任務實現(xiàn)若干靜態(tài)方法：在頭插入結點贩幻、在表尾插入結點轿腺、從表頭刪除結點、從表尾刪除結點丛楚、在指定結點前插入新結點族壳、在指定結點之后插入新結點、刪除指定結點趣些。
1.3.31 Implement a nested class DoubleNode for building doubly-linked lists, where each node contains a reference to the item preceding it and the item following it in the list (null if there is no such item). Then implement static methods for the following tasks: insert at the beginning, insert at the end, remove from the beginning, remove from the end, insert before a given node, insert after a given node, and remove a given node.
廣告
我的首款個人開發(fā)的APP壁紙寶貝上線了仿荆，歡迎大家下載。
