摘要：性质相对于数组，长度可变插入删除更容易。为了正确的反转一个链表，需要调整链表中指针的方向指针反向。注意，在单链表中，将一个节点的指向后继的指针指向它的前驱，将会导致链表的断裂。
虽是读书笔记，但是如转载请注明出处 http://segmentfault.com/blog/exploring/
.. 拒绝伸手复制党
以下是算法导论第十章的学习笔记
1 栈栈顶指针 top (初始值top = -1)指向栈顶元素，插入时先修改指针再插入，删除时先取栈顶元素再修改指针.
1.1 性质后进先出
入栈，出栈都是O(1)
javapublic class Stack {
private int[] array = new int[5];
private int top = -1;
public Boolean stackempty(){
if(top == -1){
return true;
}
else
return false;
}
public void push(int x){
if(top<=array.length-1){
array[++top] = x;
}
else{
System.out.println("overflow");
}
}
java public int pop() {
int number = -1;
if(stackempty() != true){
number = array[top];
top--;
return number;
}
else
{
System.out.println("underflow");
return -1;
}
}
2 队列
用array[n]数组实现的至多含有n-1个元素的队列的方法.
队列具有属性head[Q],指向队列的头. 属性tail[Q]指向新元素要被插入的地方
head[Q] = tail[Q]时，队列空；
head[Q] = tail[Q]+1时，队列满；
初始head[Q] = tail[Q] = 1
先进先出
入队，出队都是O(1)
javapublic class Queue {
private int[] array = new int[4];
private int head = 1;
private int tail = 1;
//入队
public void enqueue(int x){
//处理上溢
try{
if(head != tail +1){
array[tail++] = x;
if(tail == array.length){
tail = 0;
}
}
else{
System.out.println("overflow");
throw new Exception("queue overflow");
}
}catch(Exception e){
e.printStackTrace();
}
}
java //出队
public int dequeue(){
int number=0;
try{
if(tail != head){
number = array[head];
head++;
}
else{
throw new Exception("queue underflow");
}
}catch(Exception e){
System.out.println("underflow");
e.printStackTrace();
}
return number;
}
3. (双向)链表
链表是面试时被频繁提及的DS。 每个对象包括一个关键字域和两个指针域prev,next;
链表为什么这么受欢迎？
链表是一种动态的数据结构，其操作需要通过指针进行。链表内存的分配不是在创建链表时一次性完成，而是每添加一个节点就分配一次内存。由于没有闲置内存。他的空间效率比数组更高。
通过使用哨兵nil节点（增加一个nil节点）可以简化边界条件。
3.1 性质相对于数组，长度可变；插入删除更容易。
3.2核心代码（单向链表）
javapublic class LinkedList {
private Node head;
private Stack s;
LinkedList(){
head = null;
s = new Stack();
}
private static class Node{
int item;
Node next;
Node(){
this.item = 0;
this.next = null;
}
Node(int item, Node next){
this.item = item;
this.next = next;
}
}
public void insert(int x){
Node node = new Node(x, null);
Node p = head;
// 注意链表为空的时候的插入
if(head==null){
head = node;
}
// 尾插法
else{
while(p.next != null){
p = p.next;
}
p.next = node;
}
}
public void travese(Node head){
Node p = head;
while(p!=null){
System.out.println(p.item);
p = p.next;
}
}
(双向链表)
javapublic class DoubleLinkedList {
// 哨兵节点nil(作为表头指针)
private Node nil;
// 初始化一个链表
DoubleLinkedList(){
nil = new Node();
nil.next = nil;
nil.prev = nil;
count = 0;
}
// 链表长度
private int count;
private static class Node{
int item;
Node next;
Node prev;
Node(){
item = 0;
next = null;
prev = null;
}
Node(int item, Node next, Node prev){
this.item = item;
this.next = next;
this.prev = prev;
}
}
//返回当前链表的长度
public int length(){
return count;
}
//获取value为k的节点
public Node listsearch(int k){
Node result = null;
Node head = nil;
while(head.next != nil){
if(head.next.item == k){
result = head.next;
break;
}
else
head = head.next;
}
return result;
}
//插入一个节点在队首
public void listinsert(Node node){
node.next = nil.next;
nil.next.prev = node;
nil.next = node;
node.prev = nil;
count++;
}
//根据value删除一个节点
public Node listdelete(Node node){
Node head = nil;
Node nodetodelete;
while(head.next!=nil){
if(head.next.item == node.item){
nodetodelete = head.next; //将要删除的节点
head.next = nodetodelete.next;
nodetodelete.next.prev = head;
nodetodelete = null;
count--;
}
else{
head = head.next;
}
}
return node;
}
//输出链表
public void traverse(){
Node head = nil;
while( head.next!= nil){
System.out.println(head.next.item);
head = head.next;
}
}
3.3 扩展
1. 从尾到头打印链表
题目：输入一个链表的头节点，从尾到头打印出来每个节点的值。
解法：遍历，每遍历到的元素存到栈，然后输出栈即可。
代码：
java public void reveaseoutput(Node head){
Node p = head;
if(p==null){
System.out.println("empty list");
}
while(p != null){
s.push(p.item);
p = p.next;
}
while(s.stackempty()!= true){
int n = s.pop();
System.out.println(n);
}
}
2. O(1)时间删除链表节点
题目：给定单链表的头指针和一个节点指针，O(1)时间删除该链表节点
解法：下一个节点的内容复制到需要删除的点，即覆盖。然后删该店的下一个节点。
这里需要考虑两个边界条件，1 要删除的点位于尾部 2 链表只有一个节点
要考虑鲁棒性。
代码：
javapublic void deleteNode(Node head, Node pToDeleted){
if(head!=null){
//要删除的是尾节点
if(pToDeleted.next == null){
//如果要删除的是链表唯一的节点
if(head.next==null){
head = null;
System.out.println(head);
pToDeleted = null;
}
else{
Node p = head;
while(p.next!=pToDeleted){
p = p.next;
}
p.next = null;
pToDeleted =null;
}
}
//要删除的不是尾节点，且节点数大于1
else{
pToDeleted.item = pToDeleted.next.item;
pToDeleted.next = pToDeleted.next.next;
pToDeleted = null;
}
}else{
System.out.println("the linklist is empty");
}
}
3. 倒数第k个节点
题目：输入一个链表，输出该链表第倒k个节点。（链表从1开始计数）
解法：定义两个指针，第一个指针从链表的head指针开始遍历，向前走k-1步的时候，第二个指针开始和它一起走。当第一个指针的next指向null的时候，第二个指针指向了倒数第k个。（这种一次遍历，对时间要求比较高的程序，就需要借助空间，再开辟一个指针）
要考虑鲁棒性。
代码：
java //遍历链表一次，删除倒数第K个元素
public Node FindKthToTail(Node head, int k){
Node p=head;
Node q = head;
int i;
if(head==null || k==0){
return null;
}
for(i=0;i
4. 反转链表
题目：定义一个函数，输入链表头节点，反转该链表并输出反转后链表的头节点。
解法：借助三个指针，prev, p, next. 避免指针断裂。
（ 为了正确的反转一个链表，需要调整链表中指针的方向【指针反向】。注意，在单链表中，将一个节点的指向后继的指针指向它的前驱，将会导致链表的断裂。导致无法在单链表中遍历它的后继节点，因此，在调整某一节点的 next 指针时，需要首先将其的后继节点保存下来。）
代码：
java
public Node reverse(){
Node p = head;
try{
if(p!=null){
Node pnext = p.next;
p.next = null;
while(pnext!= null){
Node r = pnext.next;
pnext.next = p;
p = pnext;
pnext = r;
}
}else{
throw new Exception("empty list");
}
}catch(Exception e){
e.printStackTrace();
}finally{
return p;
}
}
5 合并链表
题目：输入两个增序的链表，合并这两个链表并使新链表仍然增序。
解法：重点强调鲁棒性：两个链表一个或者两个都是null,两个链表只有一个节点。
代码：
java public Node merge(Node head1, Node head2){
if(head1 == null) {
return head2;
}
if(head2 == null){
return head1;
}
else{
Node newhead;
Node r;
Node p = head1;
Node q = head2;
java if(head1.item <= head2.item){
newhead = head1;
p = p.next;
}
else{
newhead = head2;
q = q.next;
}
r = newhead;
while(p!=null && q!=null){
if(p.item <= q.item){
r.next = p;
p = p.next;
r = r.next;
}
else{
r.next = q;
q = q.next;
r = r.next;
}
}
if(p!=null){
r.next = p;
}
if(q!=null){
r.next = q;
}
return newhead;
}
}
6 复杂链表的复制
题目：
解法：
代码：
java //1. 根据原始链表的每个节点创建对应的copy节点
public void CloneNode(ComplexNode head){
ComplexNode p = head;
while(p!=null){
ComplexNode node = new ComplexNode(p.item,null,null);
node.next = p.next;
p.next = node;
p = node.next;
}
}
java //2. 设置复制出来的节点的sibling
public void connectsiblingnodes(ComplexNode head){
ComplexNode p = head;
while(p!=null){
ComplexNode q = p.next;
if(p.sibling!=null)
{
q.sibling = p.sibling.next;
}
p = q.next;
}
}
java //3. 拆分链表
public ComplexNode ReconnectNodes(ComplexNode head){
ComplexNode p = head;
if(p!=null){
ComplexNode newhead = p.next;
ComplexNode q = newhead;
while(q.next!=null){
p.next = q.next;
p = q.next;
q.next = p.next;
q = p.next;
}
return newhead;
}
else{
return null;
}
}
7 寻找第一个公共节点
题目：输入两个链表，找出第一个公共节点。
解法：Y形
代码：
java public Node findfirstcommonnode(Node head1, Node head2){
Node p = head1;Node q = head2;
int length = int length1 = int length2= 0;
while(p!=null){
length1 = length1 + 1;
p = p.next;
}
while(q!=null){
length2 = length2 + 1;
q = q.next;
}
p = head1;q = head2;
if(length1>length2){
length = length1 - length2;
while(length>0){
p = p.next; length--;
}
}
if(length10){
q = q.next; length--;
}
}
while(p!=null&&q!=null&&p.item != q.item){
p = p.next; q = q.next;
}
return p;
}
想更一进步的支持我，请扫描下方的二维码，你懂的~
文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。
转载请注明本文地址：https://www.ucloud.cn/yun/64294.html
摘要：在改进前使用数组的一个缺点是必须声明数组的大小，所以栈有确定的容量。待解决的问题建立一个能够增长或者缩短到任意大小的栈。下边的图是观察时间开销的另一种方式，表示了入栈操作需要访问数组的次数。 前言 上一篇：算法分析下一篇：基本排序 本篇内容主要是栈，队列 (和包)的基本数据类型和数据结构文章里头所有的对数函数都是以 2 为底关于性能分析，可能还是需要一些数学知识，有时间可以回一下在很多...
摘要：一前言上一篇已经讲过了链表实现单向链表了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用栈和队列如果写错的地方希望大家能够多多体谅并指正哦，如果有更好的理解的方式也希望能够在评论下留言，让大家学习学习二数据结构栈就是这么简单数据结构 一、前言 上一篇已经讲过了链表【Java实现单向链表】了，它跟数组都是线性结构的基础，本文主要讲解线性结构的应用：栈和队列 如果写错的地方希望大家...
摘要：栈队列双端队列都是非常经典的数据结构。结合了栈和队列的特点。因此，在中，有栈的使用需求时，使用代替。迭代器之前源码源码之与字段中分析过，容器的实现中，所有修改过容器结构的操作都需要修改字段。 栈、队列、双端队列都是非常经典的数据结构。和链表、数组不同，这三种数据结构的抽象层次更高。它只描述了数据结构有哪些行为，而并不关心数据结构内部用何种思路、方式去组织。本篇博文重点关注这三种数据结构...
摘要：会死循环，因为栈内不会弹出所以判断会一直执行。集合用于模拟队列这种数据结构，队列通常是指先进先出的容器。集合不仅提供了的功能，还提供了双端队列，栈的功能。如果有多个线程需要访问集合中的元素，需要考虑使用将几个包装成线程安全集合。 List判断两个对象相等只通过equals方法比较返回true即可。 public class A { @Override public ...
阅读 2320·2021-09-26 10:21
阅读 2794·2021-09-08 09:36
阅读 3069·2019-08-30 15:56
阅读 958·2019-08-30 12:57
阅读 923·2019-08-26 10:39
阅读 3558·2019-08-23 18:11
阅读 3083·2019-08-23 17:12
阅读 1084·2019-08-23 12:18
