链表

链表

哈希表

unordered_map的使用

既有key又有value就是map结构

1. 头文件：

   #include< unordered_map>

2. 定义一个哈希表(我们以Key和Value都是int变量为例)

   unordered_map<int,int> Hash;

3. 哈希表的建立有下面几种方法

   Hash[1]=3;
   Hash.insert<make_pair(1,3)>;
   Hash.insert({ {1,3},{2,4} });

4. 迭代器

   unordered_map<int,int>::iterator it;

5. 利用迭代器访问变量

   it->first; it->second;

6. 哈希表的查找

   it=Hash.find(1);

7. 修改哈希表

   Hash[1] = 4;

8. 清除哈希表

   Hash.erase(1); Hash.clear();

• 放入哈希表的东西：

  如果是基础类型，内部按值传递，内存占用就是这个东西的大小，如int，string

  Eg：unordered_map<int,int> Hash;unordered_map<string,string> Hash;Hash.insert<make_pair("ssdefefrf",3)>

  ​ string多大则哈希表多大，是把值直接拷贝到哈希表

  如果不是基础类型，内部按引用传递，内存大小就是这个东西内存地址大小，即8字节，如自定义的node

  ​ 不管node多大，哈希表里存放的就是node的地址

• 哈希表的增删查改操作都是常数级

有序表

哈希表能实现的功能，有序表都能实现

并且有序表的key按某种规则有序组织

有序表的增删查改操作都是O(logN)

放入有序表的东西：

如果是基础类型，内部按值传递，内存占用就是这个东西的大小

如果不是基础类型，内部按引用传递，内存大小就是这个东西内存地址大小，即8字节，并且必须提供比较器

单链表

链表由一系列结点组成

结点=数据+下一个结点的指针

链表的特点：

1. 存储空间可连续也可不连续
2. 链表的存取通过头节点开始
3. 是非随机存取的存储结构

链表的插入方式

插在头节点前还是头节点后

1. 头插法

   new->next=head;head=new;

2. 尾插法

   new->next=head->next;head->next=new;

单链表的结构

//单链表类的定义
template<class elemType>
class sLinkList{
private:
	struct node{//单链表中的结点类
		elemType data;
		node *next;
		node(const elemType &x,node *n=NULL){//结点构造函数
			data=x;
			next=n;
		}
		node():next(NULL){}//*
		~node(){};//注意要写实现
	};
	node *head;
	int currentLength;
	node *move(int i) const;//返回第i个结点的位置
public:
	sLinkList();
	~sLinkList(){
		clear();
		delete head;
	};
	void clear();
	int length(){
		return currentLength;
	}
	void insert(int i,const elemType &x);
	void remove(int i);
	int search(const elemType &x)const;
	elemType visit(int i) const;
	void traverse() const;
};


//链表构造函数
template<class elemType>
sLinkList<elemType>::sLinkList(){
	head=new node;
	currentLength=0;
}

//清除线性表
template<class elemType>
void sLinkList<elemType>::clear(){
	node *p=head->next,*q;
	head->next=NULL;

	while(p->next!=NULL){
		q=p->next;//先记录p下一个结点
		delete p;//再删除p
		p=q;
	}
	currentLength=0;
}

//返回第i个元素的指针
template<class elemType>
typename sLinkList<elemType>::node *sLinkList<elemType>::move(int i) const{
	node *p=head;
	for(int j=0;j<=i;j++){
		p=p->next;
	}
	return p;
}

//在i处插入x
template<class elemType>
void sLinkList<elemType>::insert(int i,const elemType &x){
	//i-1处的下一个结点是x
	node *pos=move(i-1);
	pos->next=new node(x,pos->next);
	currentLength++;
}

//删除第i个元素
template<class elemType>
void sLinkList<elemType>::remove(int i){
	//i-1处的下一个结点是i+1处
	node *pos=move(i-1);
	node *del=pos->next;
	pos->next=del->next;
	delete del;
	currentLength--;
}

//搜索线性表中是否出现x，找不到返回-1，找到返回x的下标
template<class elemType>
int sLinkList<elemType>::search(const elemType &x)const{
	node *p=head->next;
	for(int i=0;i<currentLength;i++,p=p->next){
		if(p->data==x) return i;
	}
	return -1;
}

//访问线性表的第i个元素
template<class elemType>
elemType sLinkList<elemType>::visit(int i)const{
	return move(i)->data;
}

//遍历运算
template<class elemType>
void sLinkList<elemType>::traverse()const{
	node *p=head->next;
	for(int i=0;i<currentLength;i++,p=p->next){
		cout<<p->data<<" ";
	}
}

//使用
sLinkList<int> list;

双链表

每个结点附加了两个指针字段，previous：前驱节点的地址，next：后继节点的地址

头节点：previous=NULL，next=a[0]

尾结点：previous=a[末]，next=NULL

template<class elemType>
class dLinkList{
private:
	struct node{//双链表的结点类
		node *prev,*next;
		elemType data;
		node(const elemType &x,node *p=NULL,node *n=NULL){
			data=x;prev=p;next=n;
		}
		node():prev(NULL),next(NULL){}
		~node(){}
	};
	node *head,*tail;
	int currentLength;
	node *move(int i);//返回i位置的结点
public:
	dLinkList();
	~dLinkList(){
		clear();
		delete head;
		delete tail;
	}
	void clear();
	int length(){
		return currentLength;
	}
	void insert(int i,elemType &x);
	void remove(int i);
	int search(const elemType &x);
	elemType visit(int i);
	void traverse();
};

template <class elemType>
dLinkList<elemType>::dLinkList(){
	head=new node;
	tail=new node;
	head->next=tail;
	tail->prev=head;
	currentLength=0;
}

template <class elemType>
typename dLinkList<elemType>::node *dLinkList<elemType>::move(int i){
	node *p=head;
	for(int j=0;j<=i;j++){
		p=p->next;
	}
	return p;
}

template <class elemType>
void dLinkList<elemType>::insert(int i,elemType &x){
	node *pos=move(i-1);//a[i-1]
	node *next=pos->next;//a[i]
	node *tmp=new node(x,pos,next);
	pos->next=tmp;
	next->prev=tmp;
	currentLength++;
}

template <class elemType>
void dLinkList<elemType>::clear(){
	node *p=head->next,*q;
	head->next=NULL;
	while(p!=NULL){
		q=p->next;
		delete p;
		p=q;
	}
	delete p;
	delete q;
	delete head;
	currentLength=0;
}

template <class elemType>
void dLinkList<elemType>::remove(int i){
	node *pos=move(i-1);
	node *del=pos->next;//a[i]
	node *next=del->next;
	pos->next=next;
	next->prev=pos;
	delete del;
	currentLength--;
}

template <class elemType>
int dLinkList<elemType>::search(const elemType &x){
	node *p=head->next;
	for(int i=0;i<currentLength;i++,p=p->next){
		if(p->data==x) return i;
	}
	return -1;
}
	
template <class elemType>
elemType dLinkList<elemType>::visit(int i){
	return move(i)->data;
}

template <class elemType>	
void dLinkList<elemType>::traverse(){
	node *p=head->next;
	for(int i=0;i<currentLength;i++,p=p->next){
		cout<<p->data<<" ";
	}
}

循环链表

一般单循环链表不设头节点，双循环链表不设头尾结点

题目

笔试：只要求时间复杂度

面试：时间复杂度优先，空间复杂度尽可能小

技巧：1、额外数据结构记录；2、快慢指针

反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

• 不要求空间

  • 准备一个栈，遍历链表进栈，出栈==原链表——>回文链表

  • 改进：让链表右边一半进栈

    • Q：怎么知道右边一半开始

      A：准备两个指针，慢指针一次走一步，快指针一次走两步，注意边界条件

• 要求空间复杂度

  • 准备快慢指针，当慢指针走到中间的时候，把后面的链表逆序，然后一块从两头向中间遍历，最后恢复链表

• 将单向链表按某值划分为左边小、中间相等、右边大的形式

  • 要求低

    • 定义一个node型的数组，进行partition，再串起来

      template<class elemType>
      void sLinkList<elemType>::partition(int aim){
      	node *arr[currentLength];
      	node *pos=head->next;
      	for(int i=0;i<currentLength;i++){
      		arr[i]=pos;
      		pos=pos->next;
      	}
      	int i=0,low=-1,high=currentLength;
      	node *temp;
      	while(i!=high){
      		if(arr[i]->data<aim){
      			temp=arr[i];
      			arr[i]=arr[low+1];
      			arr[low+1]=temp;
      			low++;
      			i++;
      		}
      		else if(arr[i]->data==aim){
      			i++;
      		}
      		else if(arr[i]->data>aim){
      			temp=arr[i];
      			arr[i]=arr[high-1];
      			arr[high-1]=temp;
      			high--;
      		}
      	}
      	head->next=arr[0];
      	for(int i=0;i<currentLength-1;i++){
      		arr[i]->next=arr[i+1];
      	}	
      	arr[currentLength-1]->next=NULL;
      }

  • 要求高

    • 定义六个变量，小于等于大于三个区域的头和尾，最后再连起来

      • 此时的partition具有稳定性

      template<class elemType>
      void sLinkList<elemType>::partition(int aim){
      	node *sh=NULL;
      	node *st=NULL;
      	node *mh=NULL;
      	node *mt=NULL;
      	node *bh=NULL;
      	node *bt=NULL;
      	node *pos=head->next;
      	while(pos!=NULL){
      		if(pos->data<aim){
      			if(sh==NULL){
      				sh=pos;
      				st=pos;
      			}
      			else{
      				st->next=pos;
      				st=pos;
      			}
      		}
      		else if(pos->data==aim){
      			if(mh==NULL){
      				mh=pos;
      				mt=pos;
      			}
      			else{
      				mt->next=pos;
      				mt=pos;
      			}
      		}
      		else if(pos->data>aim){
      			if(bh==NULL){
      				bh=pos;
      				bt=pos;
      			}
      			else{
      				bt->next=pos;
      				bt=pos;
      			}
      		}
      		pos=pos->next;
      	}
      	st->next=NULL;
      	mt->next=NULL;
      	bt->next=NULL;
      	//将三个区域连起来，注意讨论区域为空的情况
      	if(sh==NULL){
      		if(mh==NULL) head->next=bh;
      		else{
      			head->next=mh;
      			if(bh==NULL) mt->next=NULL;
      			else{
      				mt->next=bh;
      				bt->next=NULL;
      			}
      		}
      	}
      	else{
      		head->next=sh;
      		if(mh==NULL){
      			if(bh==NULL) st->next=NULL;
      			else{
      				st->next=bh;
      				bt->next=NULL;
      			}
      		}
      		else{
      			st->next=mh;
      			if(bh==NULL) mt->next=NULL;
      			else{
      				mt->next=bh;
      				bt->next=NULL;
      			}
      		}
      	}
      }	

  随机链表的复制

  给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。

  构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。

  例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。

  返回复制链表的头节点。

  用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：

  val：一个表示 Node.val 的整数。

  random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。

  你的代码 只 接受原链表的头节点 head 作为传入参数。

  • 要求低：可以使用额外空间，哈希表

    • 哈希表的key=node(old),value=node(new)

      （1）的next指向（2），则value(1)的next指向value（2）

  • 要求高：不使用哈希表

    • 克隆新节点挂在旧结点后面，加上rand指针，old->next->rand=old->rand
    • 分离新旧链表

两个单链表相交的一系列问题

题目：给定两个可能有环也可能无环的单链表，头节点head1/2，函数：若相交返回相交的第一个结点，若不相交，返回null

要求：链表长度之和为N，时间复杂度：O(N)，空间复杂度：O(1)

1.判断环

• 使用哈希
  • 准备一个set，遍历，set中有无，无则放入，有则说明是入环结点
• 快慢指针，初始都在头节点，慢指针走一步，快指针走两步
  • 快指针=null——>无环
  • 若有环，则快慢指针一定会相遇
    1. 让快指针回到头节点
    2. 快慢指针每次移动一步，则快慢指针相遇的地方就是入环结点

2.判相交结点

• 两个都无环
  • if end1!=end2 不相交
  • else 从长链表中*位开始往后走，短链表从头往后中，可得相交结点##
• 一个有环一个无环，一定不相交
• 两个都有环
  • loop1？=loop2
    • =，复用##
    • ！=，从loop1能不能走到loop2
      • 不能，不相交
      • 能，loop1和loop2都是相交结点