方下

2025/10/20 共 5341 字，约 16 分钟

链表格式

链表的结构体如下

struct ListNode{
	int val;
	struct ListNode * next;
	ListNode(int x): val(x), next(NULL){}
}

剑指offer

1. 从尾到头打印链表，以数组返回。

思想是：将链表存储的List逆序存放在数组中。用到的代码块如下：

// len of ListNode *List;
int len = 0
while(List){
	len++;
	List = List->next;
}
// define vector, and initialized with 0
vector<int> ans(len, 0); 
// fill the vector ans in reverse order
for(int i=len-1;i>=0;i--){
	ans[i]=List->val;
	List=List->next;
}

2. 反转链表

如图：

[../images/post/2024-05-23/reverse_list.excalidraw.svg]

//loop
while(head){
	tmp = head->next;//to prevent being unlinded
	head->next=cur;
	cur=head;
	head=tmp
}
return cur;

3. 两个链表的第一个公共点.

方法一、拼接 (1)两表不一定等长，长短拼接必等长； (2)等长后，两指针同时步进，相同则相遇； (3)代码中，走到尾部指向另一链表，等同与拼接。

![[two_list_commen_point.excalidraw]]

ListNode *p1=pHead1,*p2=pHead2;
while(p1!=p2){
	p1=p1->next?p1->next:pHead2;
	p2=p2->next?p2->next:pHead1;
}
return p1;

方法二、计算长度差，长表先走

int getLen(ListNode * list){
	int ans=0;
	while(list){
		list=list->next;
		ans++;
	}
	return ans;
}

int n1 = getLen(pHead1);
int n2 = getLen(pHead2);
int gap = abs(n1-n2);

if(n1>n2){
	while(n1--) pHead1=pHead1->next;
}else{
	while(n2--) pHead2=pHead2->next;
}
while(pHead1){
	if(pHead1==pHead2) break;
	pHead1=pHead1->next;
	pHead2=pHead2->next;
}
return pHead1;

4. 链表中环的入口结点

需要进行数学运算，先看带环表的结构： ![[entrance_circular_list.excalidraw]] \(slow:\; x+n(y+z)+y\) \(fast:\; x+m(y+z)+y\) \(总会相遇=> x+m(y+z)+y = 2[x+n(y+z)+y]\) \(=> (m-2n)(y+z)=x+y\) 这是什么意思呢：走一定数量的圈（y+z）会等于从表头走到相遇处。 从相遇处开始走任何数量的圈，都会到达相遇处。 一指针从表头走，一指针从相遇处走，相同速度，则必然同时到达相遇处。 因为Y在圈中，则这一段两指针同行，故两指针相遇时就是环的入口。

ListNode *slow=pHead, *fast=pHead;
int i=0;
while(slow!=fast || i++ ==0){
	if(!slow->next) return nullptr; 
	slow=slow->next;
	if(!fast->next||!fast->next->next) retunr nullptr;
	fast=fast->next->next;
}
slow=pHead;
while(slow!=fast){
	slow=slow->next;
	fast=fast->next;
}
return slow;

5. 复制复杂链表

![[copy_complex_list.excalidraw]]

链表不是简单的单链结构，还有一个随机指向的指针，结构如下：

//the struct of complex list
/*   
struct RandomListNode{
	int label;
	struct RandomListNode *next, *random;
	RandomListNode(int x): label(x), next(NULL), random(NULL){}
}
*/

方法一
(1)遍历复制结点时，用map将临时指针对应起来 (2)再遍历一遍，复制结点的random指针填入map[原结点random指针] ![[map_to_complex_list.excalidraw]]

RandomListNode *p1=pHead;
RandomListNode *p2=pHead;
map<RandomListNode *,RandomListNode*> pMap;
int i=0;
while(p1){
	auto *tmp = RandomListNode(p1->label);
	pMap[p1]=tmp;
	if(i==0){
		i++;
	}else{
		p2->next=tmp;
	}
	p2=tmp;
}
p1=pHead;
p2=pMap[p1];
while(p1){
	//pMap[p1]->random=pMap[p1->random];
	p2->random=pMap[p1->random];
	p1=p1->next;
	p2=p2->next;
}
return pMap[pHead];

这里其实有个小问题，当p1->random为nullptr时，是没有考虑到的，如链表结构图中的几点3和5。 但是map容器有一个特点，即对于map<key, value>中没有的key, 其相应的value会去0或者空值。 即，map<int, int>形式，未存储的keymap[0]=map[1]=0, map<int* int*> 类型的， map[&1]=map[&1]=nullptr， 这样当p1->random为nullptr时，恰好为未存储的key，即恰好pMap[nullptr]=nullptr。

方法二，利用原结点的next指针，将原结点和对应复制结点连接起来。 （1）原链表断开，垂直连接，遍历原链表的临时指针存入vector<*> （2）复制结点插入原链。先将将复制结点插入到原结点后边，完成random指针连接后再拆分链表。 ![[complex_list_next_pointer.excalidraw]] 代码分别如下：

(1)断链垂连

if(!pHead){//easy to foget
	return nullptr;
}
vector<RandomListNode *> pVec;
RandomListNode *p1=pHead;
RandomListNode *p2=nullptr;
int i=0;
while(p1){
	auto *tmp = new RandomListNode(p1->label);
	pVec.push_back(p1);
	p1=p1->next;
	pVec.back()->next=tmp;
	if(i==0){ 
		i++;
	}else{ 
		p2->next=tmp; 
	}
	p2=tmp;
}
for(i=0;i<pVec.size();i++){
	if(pVec[i]->random){
		pVec[i]->next->random=pVec[i]->random->next;
	}
}
p2 =  pVec[0]->next;
pVec[0]->next=nullptr; //error without the sentence
return p2;

(2)复制结点插入原链。

if(!pHead){
	return nullptr;
}
RandomListNode *cur = pHead;
while(cur){
	auto *tmp = new RandomListNode(cur->label);
	tmp-next=cur->next;
	cur->next=tmp;
	cur=tmp->next;
}
cur=pHead;
while(cur){
	if(cur->random){
		cur->next->random=cur->random->next;
	}
	cur=cur->next->next;
}
cur=pHead->next;
RandomListNode *ans = pHead->next;
while(cur && cur->next){
	cur->next=cur->next->next;
	cur=cur->next;
}
pHead-next=nullptr;//error without the sentence
return ans;

6. 删除链表中的结点

这类题目注意一点：new一个前置结点，因为被删除的有可能是第一个结点。 以删除连续结点为例，说明如下。 ![[delete_node_list.excalidraw]] 方法有三： (1)空间换时间，vector(n，0)下标代表val，用下标记录每个val出现的次数，再遍历一遍删除次数大于1的结点，O(n)，O(n)。 (2)双循环设置，第一层推进指针从头到尾，第二层循环删除所有连续的结点，两层循环共用指针，O(1)，O(n) (3)设置tail指针，只保留非重结点，cur指针一路前行，只要与前或者后结点相同，则不停留。前后皆不同，才用tail指针指过来。 代码分别为： (1)

if(!pHead){
	return nullptr;
}
vector<ListNode*> pVec(1001,0);
ListNode *p=pHead;
while(p){
	pVec[p->val]++;
	p=p->next;
}
auto *preAns = new ListNode(0);
ListNode *pre = preAns;
p=pHead;
while(p){
	if(pVec[p->val]==1){
		pre=p;
	}else{
		pre->next=p->next;	
	}
	p=p->next;
}
return preAns->next;

（2）

if(!pHead){
	return nullptr;
}
auto *preAns = new ListNode(0);
preAns->next=pHead;
ListNode *cur=preAns;
while(cur->next){
	if(cur->next->val==cur->next->next->val){
		int tmp=cur->next->val;
		while(cur->next && cur->next->val==tmp){
			cur->next=cur->next->next;
		}
	}else{
		cur=cur->next;
	}
}
return preAns->next;

这里要注意的是：cur如果在判断结点前面，cur->next是工作指针，此时要尤其注意下面这条语句 cur->next=cur->next->next，因为，它包含两层含义，(1)是链表删除了一个结点(2)工作指针向前移动了一位。 此时尤其要注意不能使用cur=cur->next这条语句，这样工作指针cur->next就向前移动了两次，跳过一个结点。 （3）

if(!pHead){
	return nullptr;
}
auto *preAns=new ListNode(0);
preAns->next=pHead;
ListNode *tail=preAns;
ListNode *p1=preAns;
ListNode *p2=pHead;
while(p2->next){
	if(p2->val!=pre->val && p2->val!=p2->next->val){
		tail->next=p2;
		tail=tail->next;
	}
	p1=p2;
	p2=p2->next;
}
if(p2->val==pre->val){
	tail->next=nullptr;
}else{
	tail->next=p2;
}
return preAns->next;

文档信息

Search

    Table of Contents