双指针的技巧

在面试中,链表相关的问题出现频率非常高,而很多问题都有一些类似的技巧,今天分享快慢指针的技巧。

返回链表的中间节点

题目:

1
2
给定一个带有头结点 head 的非空单链表,返回链表的中间结点。
如果有两个中间结点,则返回第二个中间结点。

分析:
这题最容易想到的做法就是先获取到链表的长度L,如果链表长度是偶数,那么中间节点就是L/2 + 1,如果是奇数,则是L/2。同样的,这种方法需要遍历两次链表。那么使用快慢指针怎么做呢?

  • 快慢指针同时指向头节点,快指针走两步,慢指针走一步
  • 如果长度为偶数,那么快指针为NULL的时候停止,长度为奇数,fast->next为NULL的时候停止
  • 慢指针指向的位置就是中间节点了

按照这种思路,实现代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//来源:公众号【编程珠玑】
//作者:守望先生
LinkNode *findMidNode(LinkNode *head)
{
LinkNode *fast = head;
LinkNode *slow = head;
while (NULL != fast && NULL != fast->next )
{
fast = fast->next->next;
slow = slow->next;
}
return slow;
}

链表的中间节点

题目:

1
2
3
4
5
6
7
题目:
输入一个单向链表,输出该链表中倒数第k个结点。为符合计数习惯,本题从1开始计数,即链表的尾节点是倒数第1个节点。
例子
如:一个链表有6个节点,从头节点开始,它们的值依次是1、2、3、4、5、6。这个链表的倒数第3个节点是值为4的节点。

分析:
由于单向链表并不能从末尾开始数,因此没有办法直接得出倒数第k个节点。但是这也不难,我们可以计算出链表的长度l,然后再从头数到l-k,即可得到倒数第k个节点。

但是这种方法需要遍历两次!有没有遍历一次的方法呢?

思路:
定义两个指针,指针移动一个快,一个慢
1.快慢指针同时指向头结点
2.首先快指针移动k-1步,先走到第k个节点
3.快慢指针同时移动,直到快指针指向末尾,这时,快慢指针都走了l-k,
4.慢指针指向的节点即为我们需要寻找的节点

举个例子,有链表值依次为1,2,3,4,5,6,找到倒数第三个节点:

先让快指针移动3-1步。

1 2 3 4 5 6
slow fast

然后快慢同时移动,直到fast到达末尾:

1 2 3 4 5 6
slow fast

看到了吗,这时候slow就指向了倒数第三个节点。

我们的参考代码实现如下:

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
//来源:公众号【编程珠玑】
//作者:守望先生
//https://www.yanbinghu.com
LinkNode *FindKthToTail(LinkNode *head,unsigned int k)
{
if(NULL == head || 0 == k)
return head;
LinkNode *pFast = head;
LinkNode *pSlow = head;
unsigned int i = 0;
//快指针先移动
while(i < k -1)
{
if(NULL != pFast)
{
pFast = pFast->next;
}
//k大于链表的长度
else
{
return NULL;
}
i++;
}
//快慢指针一起移动
while(NULL != pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}

判断链表是否有环

题目:如何判断一个单链表是否有环?若有环,如何找出环的入口节点。

按照快慢指针的思路,使用两个指针,一个指针每次走一步,另一个每次走两步,如果链表有环,那么它们终将相遇,而如果没有环,快的指针最后会指向NULL。
按照这种思路,我们的参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//来源:公众号【编程珠玑】
//作者:守望先生
//0:无环,1:有环
int hasLoop(LinkNode *head)
{
if(NULL == head)
return 0;
LinkNode *slow = head;
LinkNode *fast = head->next;
//当快指针到末尾时,无环,结束
while (NULL != fast && NULL != slow)
{
//快慢相遇,有环
if (fast == slow)
return 1;
slow = slow->next; // 慢指针每次走一步
fast = fast->next;
if (fast != NULL)
fast = fast->next;
}
return 0;
}

完整可运行参考代码

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
//来源:公众号【编程珠玑】
//作者:守望先生
#include <stdio.h>
#include <stdlib.h>
typedef int NodeVal;
typedef struct LinkNode_t
{
NodeVal val;
struct LinkNode_t *next;
}LinkNode;
LinkNode *createLinkNode(NodeVal *arr,size_t n){
LinkNode *head = NULL, *node = NULL, *end = NULL;//定义头节点,普通节点,尾部节点;
for (size_t i = 0; i < n; i++) {
node = (LinkNode*)malloc(sizeof(LinkNode));
//创建头节点
if(NULL == head)
{
head = node;
head->val = arr[i];
end = head;
}
else
{
node->val = arr[i];
end->next = node;
end = node;
}
}
end->next = NULL;//结束创建
return head;
}
//释放资源
void destoryLinkNode(LinkNode *head)
{
LinkNode *pn = NULL;
while (NULL != head)
{
if(NULL == head->next)
{
free(head);
head = NULL;
}
else
{
pn = head->next->next;
free(head->next);
head->next = pn;
}
}
}
LinkNode *FindKthToTail(LinkNode *head,unsigned int k)
{
if(NULL == head || 0 == k)
return head;
LinkNode *pFast = head;
LinkNode *pSlow = head;
unsigned int i = 0;
//快指针先移动
while(i < k -1)
{
if(NULL != pFast)
{
pFast = pFast->next;
}
//k大于链表的长度
else
{
return NULL;
}
i++;
}
//快慢指针一起移动
while(NULL != pFast->next)
{
pSlow = pSlow->next;
pFast = pFast->next;
}
return pSlow;
}
int hasLoop(LinkNode *head)
{
if (head == NULL)
return 0;
if(NULL == head)
return 0;
LinkNode *slow = head;
LinkNode *fast = head->next;
//当快指针到末尾时,无环,结束
while (NULL != fast && NULL != slow)
{
//快慢相遇,有环
if (fast == slow)
return 1;
slow = slow->next; // 慢指针每次走一步
fast = fast->next;
if (fast != NULL)
fast = fast->next;
}
return 0;
}
void printLinkNode(LinkNode *head)
{
while(NULL != head)
{
NULL == head->next?printf("%d\n",head->val):printf("%d->",head->val);
head = head->next;
}
}
int main(void)
{
NodeVal arr[] = {1,2,3,4,5,6};
LinkNode *head = NULL;
head = createLinkNode(arr,sizeof(arr)/sizeof(NodeVal));
printLinkNode(head);
LinkNode* findNode = FindKthToTail(head,3);
if(NULL != findNode)
printf("val %d\n",findNode->val);
destoryLinkNode(head);
return 0;
}
守望 wechat
关注公众号[编程珠玑]获取更多原创技术文章
出入相友,守望相助!