链表中面试常考题

单链表如何逆置

方法一

无限头插：使用两个指针
1.安全性处理（有效长度至少大于2）
2.申请两个指针，指向第一个有效节点和第二个有效节点
3.断开头节点
4.通过p，q配合将所有节点头插进

代码：

void Reverse(struct Node *plist)
{
	assert(plist != NULL);
	int length = GetLength(plist);//保存最少有两个有效节点，才需要去逆置
	if(length < 2)
	{
		return;
	}

	//1.申请两个指针p和q，分别指向第一个有效节点和第二个有效节点
	struct Node *p = plist->next;
	struct Node *q = p->next;

	//2.断开头结点
	plist->next = NULL;

	//3，通过p和q配合，将所有节点依次头插进来
	while(p != NULL)
	{
		q = p->next;
		p->next = plist->next;
		plist->next = p;
		p = q;
	}

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

方法二

不借助头节点，需要使用三个指针，互相搭配处理。

1.安全性处理（有效结点长度至少大于2）
2.申请三个指针p,q,r分别指向第一个第二个第三个有效结点。
3.将p指向的节点的next域提前置为NULL(p指向的第一个节点，一旦逆置结束，就是尾结点，所以next域提前置为NULL)
4.在不使用头结点的情况下，将所有节点的next域反转。
5.将已经逆置结束的单链表的有效节点，重新让头结点指向回来。
代码：

void Reverse2(struct Node *plist)
{
	assert(plist != NULL);
	int length = GetLength(plist);//保存最少有两个有效节点，才需要去逆置
	if(length < 2)
	{
		return;
	}

	//1.申请三个指针p和q和r，分别指向第一个有效节点和第二个有效节点以及第三个有效节点
	struct Node *p = plist->next;
	struct Node *q = p->next;
	struct Node *r = NULL;


	//2.将p指向的节点的next域提前置为NULL(p指向的第一个节点，一旦逆置结束，就是尾结点，所以next域提前置为NULL)
	p->next = NULL;

	//3.在不使用头结点的情况下，将所有节点的next域反转
	while(q != NULL) //只能用q
	{
		r = q->next;
		q->next = p;
		p = q;
		q = r;
	}

	//4.将已经逆置结束的单链表的有效节点，重新让头结点指向回来
	plist->next = p;

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

如何判断两个单链表是否存在交点，如果存在找到第一个相交点？

思路

如何判断是否存在交点？
分别申请指针p,q,让指针p跑到单链表1的结尾处，让指针q跑到单链表2的结尾处，然后判断p和q指向的尾结点是否是用一个结点即可。
如果存在交点，如何找到相交点？

先获取两条单链表各自的长度，用len1和len2保存，再然后讲指针p指向较长的单链表的头节点，讲指针q指向较短的单链表的头节点。
然后，让指针p提前出发，向后走|len1-len2|步，则这时，指针p和指针q分别对于尾结点的距离相等。则这是，p和q同步向后走，每走一步进行一次判断p，q是否指向同一结点，如果是，则找到了第一个相交点。

代码

struct Node* Is_intersect(struct Node *plist1, struct Node *plist2)
{
	//assert plist1 plist2
	struct Node *p = plist1;
	struct Node *q = plist2;
	for(; p->next!=NULL; p=p->next);
	for(; q->next!=NULL; q=p->next);

	if(p != q)
	{
		return NULL;
	}

	//反之，存在相交点
	int len1 = GetLength(plist1);
	int len2 = GetLength(plist2);
	p = len1>len2 ? plist1 : plist2;
	q = len1>len2 ? plist2 : plist1;

	for(int i=0; i<abs(len1-len2); i++)
	{
		p = p->next;
	}
	//此时，p和q,相较于尾结点的长度是一致的,这时，依次判断即可

	while(p != q)//p和q同步向后走，如果p和q还没相遇，同时向后走一步，直到相遇，相遇点就是第一个相交点
	{
		p=p->next;
		q=q->next;
	}
	return p;//return q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

单链表是否存在一个环，如果存在找到如环点。

思路

判断是否存在环？
经典方法：用快慢指针，两个指针，一个走得快，一个走得慢，
验证方式：让快慢指针同时指向头节点，然后同步向后走，快指针一次走两步，慢指针一次走一步。当不存在环时：快指针肯定不会和满指针二次相遇，且快指针一定在慢指针之前先指向NULL地址。当存在环时：快指针会先于慢指针进入环内，但是由于快指针在环内出不来，一直打转，则当慢指针也进入到环内的时候，在环内会和慢指针二次相遇。

怎么找到如环点？
申请两个指针p和q，让p指向头节点，让q指向快慢指针相交点。接下来以同样速度向后走，这时速度一致，距离也一致。p与q相遇点便是入环点。
找到入环点的推演过程：
头节点至入环点距离为x，入环点至快慢指针相遇点为y，相遇点继续向前走，遇到入环点的距离为z。
快指针移动距离：fast=x+n（y+z）+y;
慢指针：x+y；
同样的时间，快指针是慢指针速度的二倍，因此快指针移动距离是慢指针移动距离的二倍。
fast=2slow–>x+n(y+z)+y=2(x+y)
化简得：n(y+z)=x+y
(n-1)(y+z)+y+z=x+y
x=(n-1)(y+z)+z
这个公式便是头节点到入环点的距离等于（n-1）圈加上快慢指针相遇点到入环点的距离之和。

代码

struct Node* Is_Circle_FirstNode(struct Node *plist)
{
	//0.安全性处理
	assert(plist != NULL);
	if(IsEmpty(plist))
	{
		return NULL;
	}

	//1.申请两个指针fast 和 slow
	struct Node *fast = plist;
	struct Node *slow = plist;

	slow = slow->next;
	fast = fast->next;
	if(fast != NULL)
	{
		fast = fast->next;
	}

	//2.同步向后走
	while(fast!=slow && fast!=NULL)//快慢指针还没有二次相遇且快指针也没有指向NULL
	{
		//快指针一次走两步，慢指针一次走一步
		slow = slow->next;
		//fast = fast->next->next; //error //一次跨越太多容易扯着蛋
		//注意：1.快指针不要一次将两步走完，因为第一步能不能走踏实还是个问题
		//      2.两步可以分开走，先走一步，走踏实了，再走一步
		fast = fast->next;
		if(fast != NULL)
		{
			fast = fast->next;
		}
	}

	//3.while循环退出，注意退出条件：fast!=slow && fast!=NULL
	//      如果是因为快慢指针相遇，则代表存在环，则接着要判断入环点
	//      如果是快指针先指向了NULL，则代表不存在环，则直接退出函数
	if(fast == NULL)
	{
		return NULL;
	}

	//如果上面if没有进去，则代表有环，接下来需要找入环点
	//4.找入环点，申请p和q，p指向头结点，q指向快慢指针相遇点
	struct Node *p = plist;
	struct Node *q = fast; //q=slow

	while(p != q)//如果p和q还未相遇，则保持同样速度，向后走
	{
		p = p->next;
		q = q->next;
	}

	//当while循环退出的时候，则p和q相遇，且相遇点就是我们要找的入环点
	return p; //return q;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

单链表，给一个随机结点的地址，如何在O(1)时间内，删除这个结点，（该随机结点不能是尾结点）

思路

狸猫换太子
题中让删除该节点，我们在O(1)时间复杂度内肯定不能正常删除该节点，为此，我们可以删除该节点的下一个结点，将下一个结点的数据传递给该该节点。(该方法局限性，不能是尾结点)
操作：删除下一个节点代替该节点，但需要将该结点的值改为下一个结点的值。
代码：

bool Del_Rand_Node(struct Node *del_node)
{
	//assert
	assert(del_node!=NULL);
	//狸猫换太子
	if(del_node->next == NULL)//狸猫得存在
	{
		return false;
	}

	//狸猫换太子
	del_node->data = del_node->next->data;//将狸猫化妆为太子
	struct Node *p = del_node->next;//让p指向狸猫
	del_node->next = p->next;//跨越指向
	free(p);//释放待删除节点

	return true;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19