Algorithm(4) linked list

这一块主要记录一下链表相关的一些常考题目以及解题思路。

基本知识

这一块的难点主要是考察代码的实现能力,链表相关的题目在思路上比较简单,链表上每一个元素都存储空间都是临时分配的,每一个节点在存储空间的物理位置上是不一定连续的。链表的问题,在实现的时候,最优解往往不是使用额外的数据结构,这往往需要更多的技巧(最基本的比如链表的翻转)

在分类上

  • 按照链表链接的方向,可以分为单链表以及双链表。对于单链表,每个节点只能通过其next指针指向下一个节点,双链表的每个节点,除了next指针之外,还有一个previous指针,可以指向它的前一个节点,通过当前节点,既可以找到前一个节点,也可以找到后一个节点。
  • 按照有环以及无环分类,又可以分成普通链表(无环)以及循环链表(有环),循环链表是首尾相接的链表,循环链表的最后一个元素的next指针会指向其第一个元素,循环链表的第一个元素的previous指针会指向其最后一个元素。

实现上的注意问题

  • 链表调整函数的返回值类型,根据要求,往往是节点的类型
  • 处理链表的过程中,需要采用画图的方式,来使得整个逻辑尽量清晰
  • 边界条件的处理要严格(头结点 尾节点 空节点)

链表插入和删除的注意事项

  • 特殊处理链表为空,或者链表长度为1的情况
  • 注意插入和删除的时候,要找到插入位置和删除位置的前一个节点,在头尾部进行插入和删除操作的时候需要特殊考虑
  • 双链表的时候还需要考虑previous指针的情况

单链表翻转的操作(需要同时记录 previous节点 now节点 next节点 三个位置)

  • 用临时变量记录下now节点的下一个节点的位置
  • now节点的next指针指向前一个节点 now节点变为新的head节点
  • 循环以上操作,最后返回最新的head节点

实现上的注意事项

listnode类的题目,总是做起来不爽,因为要自己定义结构体还有组链表什么的。其实还是有点不熟悉。

自己定义结构体,注意初始化的函数。

1
2
3
4
5
typedef struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
}ListNode;

还有就是初始化的时候 申请空间 给初始的空间赋值这些操作
ListNode *h=(ListNode*)malloc(sizeof(ListNode)); h->next=NULL;(事实上 这里的初始化赋值的操作完全可以根据链表的定义来进行,在定义的时候,就把初始化的操作写清楚了)

注意根据题目的要求,看链表在定义的时候究竟需不需要包含头结点,一般头结点就放在那里不动了,之后设置一个temp指针,来不断向后移动,用于执行具体的操作。

关于退出条件以及一些细节,在进行h->next这种操作之前,一定要判断是否h指针是否为NULL,要不然总会在莫名奇妙的地方出现问题。

一些常用的tips

  • 这块的操作确比较繁琐,在初始话的时候最好使用构造函数的形式head=new ListNode(val);以免造成忘记初始化为NULL
  • head指针太关键了,所有操作也都是从head指针开始的,不管是循环的还是非循环的,都要保存一个head指针,根据题目的实际情况判断头结点设置为空节点,还是第一个元素所在位置的节点。(比如后面的删除值为val的节点的题目)
  • 注意保存lastNode,即是当前节点的上一个节点,许多操作都是lastNode和currentNode结合起来进行的
  • 插入,删除的时候,改变指针也都是先改变后面的再改变前面的

链表遍历的注意事项

为何链表的题目容易做错,既然思路不难,关键就在规范性上,在细节上面。比如遍历链表的操作,模式很简单,但是总是忘记tail指针,直接每次去拿头节点遍历,然后发现,要保存head指针,之后又调,总之,大多数的时候都是应为细节注意不到位带来的错误,还有比如链表节点的初始化等等。在这里规范一下遍历的思路。

1
2
3
4
5
6
7
//给定了链表的头指针 head
//这里一定要注意 遍历的时候是用另外一个tail指针进行 头节点指针保持不变
ListNode *tail=head;
while(tail!=NULL){
//do sth (create or some operations) for tail node
tail=tail->next;
}

在实际实现的时候,有好多题目会借用到两指针的相关思路

有序的环形单链表中插入新的元素

用两个index保存有当前元素和下一个元素的位置,开始的时候,一个在头结点,一个在第一个位置,之后两个指针同时向后移动,要是发现了合适的位置(insert值比前一个大 比后一个小)就插入元素。要是没有发现,就将最终的值插入到头结点和尾节点之间,此时插入的元素可能是所有元素里面最小的,也有可能是所有元素里面最大的。

如果插入元素是所有里面最小的,还是返回当前这个元素的位置,如果是所有元素里面最大的,返回原来头结点的位置。

这个题目在做的时候,总是报您的程序打印了太多的内容,暂时不知到错在哪里(估计还是哪里有死循环???),以下是源码:

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
129
130
131
132
133
134
135
136
137
138
139
140
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class InsertValue
{
public:
ListNode* insert(vector<int> A, vector<int> nxt, int val)
{
// write code here
int i,len,num;
len=A.size();
int nxtIndex=0;
int currVlue;
ListNode *lastNode=NULL;
ListNode *currNode=NULL;
ListNode *head=NULL;
if (len==0)
{
head=new ListNode(val);
head->next=head;
return head;

}
//lastNode could be the head node
head=new ListNode(-1);
lastNode=head;
nxtIndex=0;
num=0;
while(num<len)
{
currVlue=A[nxtIndex];
currNode=new ListNode(currVlue);
lastNode->next=currNode;
lastNode=currNode;
num++;
nxtIndex=nxt[nxtIndex];
}
//could be a circle
if(nxtIndex==0)
{
currNode->next=head->next;
}
//debug
ListNode *temp;
temp=head;
for(i=0; i<num+num; i++)
{
printf(" %d",temp->val);
temp=temp->next;
}
putchar('\n');
//debugok
lastNode=head->next;
currNode=head->next->next;
bool ifInsert=false;
while(true)
{
if (currNode->next==NULL)
{
break;
}
//problem here
//same value but different address??
if (currNode->next==head->next)
{
break;
}
if((lastNode->val<=val)&&(currNode->val>=val))
{
ListNode *insertNode=new ListNode(val);
lastNode->next=insertNode;
insertNode->next=currNode;
ifInsert=true;
break;
}
lastNode=lastNode->next;
currNode=currNode->next;
}
if (ifInsert)
{
return head->next;
}
if(val>currNode->val)
{
ListNode *insertNode=new ListNode(val);
insertNode->next=currNode->next;
currNode->next=insertNode;
return head->next;
}
else
{
ListNode *insertNode=new ListNode(val);
insertNode->next=head->next;
head->next=insertNode;
if(currNode->next!=NULL)
{
currNode->next=insertNode;
}
return head->next;
}
}
};
int main()
{
int A[10]= {1,3,4,5,7};
int nxt[10]= {1,2,3,4,0};
vector<int> va;
vector<int> vnxt;
int i;
for(i=0; i<5; i++)
{
va.push_back(A[i]);
vnxt.push_back(nxt[i]);
}
InsertValue iv=InsertValue();
//debug
ListNode *temp;
ListNode *head;
head=iv.insert(va,vnxt,0);
int num=5;
temp=head;
for(i=0; i<num+num+num; i++)
{
printf(" %d",temp->val);
temp=temp->next;
if (temp==head){
break;
}
}
//debugok
return 0;
}

删除链表中的节点(简单但是不容易想到 有种跳跃思维在里面)

给定一个链表中的节点node,但不给定整个链表的头结点,如何在链表中删除node?
只有一些简单的替代思路,暂时还没有更好的办法。

替代思路:
如果是双链表的情况,会比较容易处理,直接根据当前节点的preious以及next指针找到前一个元素以及后一个元素,之后把这两个元素的指针进行对应的调整,可以删除掉当前元素。

如果是单链表的情况,比如 1->2->3 这种情况,比如要删除值为2的节点,此时可以用节点3的值覆盖掉节点2之后把节点3删除,这仅仅是逻辑上的删除,不是真正意义上的删除,因为这种操作是通过值拷贝来进行的。

这种操作的问题是,无法删除最后一个节点,比如无法删除3号位置的节点。而且在实际工程中,每个节点所代表的意义并不相同,比如每个节点如果代表一个一个的服务器,这种copy可能无法把全部的依赖都copy过去,比如节点3的环境可能无法完全在节点2上重现,这个时候,把节点3删除了会带来未知问题。

代码实际上比较trick,仅仅是一种模拟的情况

1
2
3
4
5
6
7
8
9
10
11
12
class Remove {
public:
bool removeNode(ListNode* pNode) {
// write code here
if(pNode->next==NULL){
return false;
}
pNode->val=pNode->next->val;
pNode->next=pNode->next->next;
return true;
}
};

调整链表元素的位置(partition)

给定一个链表的头结点head,再给定一个数字num,请把链表调整成节点值小于num的节点都放在链表的左边,值等于num的节点都放在链表的中间,值大于num的节点都放在链表的右边。(虽然比较简单 还是一下想不到 多少有点豁然开朗的感觉)

考察的重点代码实现不出错的能力

思路一:
使用额外的数组,将链表中的元素放到数组中。之后类似荷兰国旗问题,对数组进行一次partition,之后再还原为链表。

思路二:
思路一其实没有发挥链表的优势:拆分灵活,实质上只需要在遍历链表的时候,把原来的大链表拆分成三个小的链表就可以了,拆分之后再讲这三个小的链表串起来,灵活方便,也不容易出错。

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
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class Divide
{
public:
int ifempty(ListNode *head)
{
if (head->next==NULL)
{
return true;
}
else
{
return false;
}
}
ListNode* listDivide(ListNode* head, int val)
{
ListNode *heada=new ListNode(-1);
ListNode *headc=new ListNode(-1);
ListNode *taila=heada;
ListNode *tailc=headc;
ListNode *returnHead;
ListNode *temp=head;
if (temp->next==NULL){
return head;
}
while(temp!=NULL)
{
ListNode *newnode=new ListNode(temp->val);
if(temp->val<=val)
{
taila->next=newnode;
taila=newnode;
}
else
{
tailc->next=newnode;
tailc=newnode;
}
temp=temp->next;
}
if (ifempty(heada)==false)
{
returnHead=heada->next;
taila->next=headc->next;
}
if(ifempty(heada)==true && ifempty(headc)==false)
{
returnHead=headc->next;
}
return returnHead;
}
};
int main()
{
int a[5]= {360,220,2};
int val=2;
int i;
ListNode *head=new ListNode(360);
ListNode *tail=head;
ListNode *returnHead;
for(i=1; i<3; i++)
{
ListNode *temp=new ListNode(a[i]);
tail->next=temp;
tail=temp;
}
tail=head;
while(tail!=NULL)
{
printf(" %d",tail->val);
tail=tail->next;
}
putchar('\n');
Divide d;
returnHead=d.listDivide(head,val);
tail=returnHead;
while(tail!=NULL)
{
printf(" %d",tail->val);
tail=tail->next;
}
return 0;
}

两个链表的公共部分(这个没有要求公共部分连续 降低了一些难度)

给定两个有序链表的头结点head1以及head2,求两个有序链表的公共部分。

其实思路也很简单,就是类似于之前的两指针的思路。

是指上是两指针问题的一个链表版本的实现。

首先是前提条件判断,如果为空的时候,就直接返回空,之后index1与index2都从头开始往后遍历,如果两个元素的值相等,则打印,之后两个index全都后移,否则,值稍微小一点的那个链表的index向后移动,重复前面的逻辑。

代码实现起来倒是比较简单,注意开始时候的空值判断

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
class Common
{
public:
vector<int> findCommonParts(ListNode* headA, ListNode* headB)
{
vector<int> common;
if (headA->next==NULL||headB->next==NULL)
{
return common;
}
ListNode *tailA=headA;
ListNode *tailB=headB;
while(tailA!=NULL&&tailB!=NULL)
{
if(tailA->val==tailB->val){
common.push_back(tailA->val);
tailA=tailA->next;
tailB=tailB->next;
continue;
}else if(tailA->val<tailB->val){
tailA=tailA->next;
continue;
}else{
tailB=tailB->next;
continue;
}
}
return common;
}
};

链表局部逆序(比较灵活 综合性较强)

给定一个链表的头结点head,实现一个调整单链表的函数,使得每K个节点之间逆序,如果最后不够K格节点一组,则不调整最后的几个节点。

比如链表 1->2->3->4->5->6->7->8->null K=3 进行调整之后,就会变成3->2->1->6->5->4->7->8->null 因为最后两个元素的个数加起来没有组成3,所以最后两个节点不够一组。
说起来简单做起来难,总之有好多边界情况需要考虑,这块可能隐藏着的坑比较多。

思路一:
其实有点综合题的感觉,涉及到逆序类的题目,可以很自然的联想到逆序的操作,比如前面K个元素先入栈,之后再反向一一弹出,每次弹出的时候,需要链表的next指针进行重连,具体涉及到的细节比较多。

注意最后元素不足k个的时候,应该如何处理。
组与组之前需要经行连接,需要记下上一组中的最后一个元素。
返回调整时候链表的头结点,函数应该返回链表的头结点。

思路二:
与方法一类似,就是省去了栈的这种额外结构,依然是搜集到k个元素就进行一次k个元素之间的逆序操作。每组逆序之后的头节点和上一组已经调整好的尾节点相连。

总的来说,使用栈的话,实现上还是会简单一些,下面是相关代码,做题的时候还是要仔细一点,别把stack与vector两个结构给弄混了。。。:

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std;
struct ListNode
{
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class KInverse
{
public:
ListNode* inverse(ListNode* head, int k)
{
ListNode *tail=head;
ListNode *newhead=new ListNode(-1);
ListNode *newtail=newhead;
stack<ListNode*> help;
while(tail!=NULL)
{
help.push(tail);
tail=tail->next;
if (help.size()==k)
{
//pop and link to new list
while(help.empty()==false)
{
ListNode *temp=help.top();
help.pop();
newtail->next=temp;
newtail=newtail->next;
}
}
}
//extra element in stack
ListNode *lastone;
if(help.empty()==false){
lastone=help.top();
help.pop();
lastone->next=NULL;
}
while(help.empty()==false) {
ListNode *temp=help.top();
help.pop();
temp->next=lastone;
lastone=temp;
}
newtail->next=lastone;
return newhead->next;
}
};
int main(){
int a[10]={1,2,3,4,5,6,7,8};
ListNode *head=new ListNode(a[0]);
int i;
ListNode *tail=head;
for (i=1;i<8;i++){
ListNode *temp=new ListNode(a[i]);
tail->next=temp;
tail=tail->next;
}
tail=head;
while(tail!=NULL){
printf(" %d",tail->val);
tail=tail->next;
}
putchar('\n');
KInverse k;
ListNode *newhead=k.inverse(head,3);
tail=newhead;
while(tail!=NULL){
printf(" %d",tail->val);
tail=tail->next;
}
return 0;
}

删除值为val的节点

给定一个单链表的头节点head,链表中的每个节点保存一个整数,再给定一个值val,把左右值等于val的节点全部删掉。(注意边界条件 仅有一个节点的时候怎么处理)

思路上不难,把整个过程看做是一个新链表的构造过程,还是细节,如果当前的这个节点是val,就直接抛弃,否则就接到新节点的末尾。

注意设置专用头结点的小技巧:
这个题目在给的时候,头结点的位置实际上是第一个元素,这种问题给法在实际处理的时候很不方便,应为总是要考虑第一个元素的特殊情况,后面case的处理方式无法和第一个统一起来,这个时候可以对原来的链表进行适当的“扩展”,就是扩展出一个realHead,作为真正的头结点,让realHead的next值指向第一个存储了元素的节点,即head,prev指针开始的时候就放在realHead的这个位置上,这样后面的情况处理起来就可以用一个逻辑进行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class ClearValue {
public:
ListNode* clear(ListNode* head, int val) {
// write code here
ListNode *realHead=new ListNode(-1);
realHead->next=head;
ListNode *prev=realHead;
ListNode *curr=head;
int temp;
while(curr!=NULL){
temp=curr->val;
if(temp==val){
prev->next=curr->next;
delete(curr);
curr=prev->next;
}else{
curr=curr->next;
prev=prev->next;
}

}
return realHead->next;
}
};

判断一个链表是否为回文结构(后面两种方法很有启发性)

比如:链表 1-2-3-2-1 是回文结构,返回true,链表1-2-3-1不是回文结构,返回false。

思路1

借用栈,第一次遍历,把元素压入栈中,第二次遍历,栈中元素同时也向外弹出,一次比较,如果比较到最后,所有的元素都相等,说明是回文结构。(实现上是最简单的)
代码如下,注意stack的基本操作:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Palindrome {
public:
bool isPalindrome(ListNode* pHead) {
// write code here
stack<ListNode*> s;
ListNode*tail=pHead;
while(tail!=NULL){
s.push(tail);
tail=tail->next;
}
tail=pHead;
ListNode*temp = NULL;
while(tail!=NULL){
temp=s.top();
if (temp->val!=tail->val){
return false;
}
tail=tail->next;
s.pop();
}
return true;
}
};

思路2

思路1的升级版本,采用快指针和慢指针两个指针,慢指针一次向后移动一个元素,快指针一次向后移动两个元素,慢指针每次移动到的元素入栈。当快指针移动到末尾的时候,如果链表的个数奇数,就不入栈,如果为偶数则入栈,之后慢指针再向后移动,同时弹出栈中元素,依次比较是否相等,判断是否为回文链表。相当于是把链表左半部分折过来与链表的右半部分进行比较。

思路3

找到链表中间的位置,之后把链表右半部分逆序,之后采用两指针的思路,从链表的两端向中间的位置遍历,链表将被调整成这样的结构:1->2->3<-2<-1

random指针(较难 链表的拆分 拷贝)

一个链表结构中,每个节点不仅含有一条指向下一个节点的next指针,同时含有一条random指针,random指针可能指向链表当中的任意一个节点(可前可后),请复制这种含有random指针节点的链表。

这个题目的难点在与random指针的复制,比如新copy了一个节点,这个时候,如何让新节点的random指针指过去的元素也是新copy出来的,这是这个题目的难点所在。

思路:

  • 遍历链表,每次遍历的时候,复制一个元素在后面,比如原先的链表为1->2->3,复制操作之后变为1->1’->2->2’->3->3’,这种结构的一个特殊性,或者说是规律性就在与,新copy出来的元素的位置在原来的老元素的下一个位置(这一点是相当关键的)
  • 之后开始指针的复制,通过1’的random指针,可以找到原来1节点指向的元素位置,比如说是3,那么3的下一个位置就是3’,这个时候,就可以找到3’,将1’的random指针调整过去,依次这样进行,就可以完成所有的random指针的调整。
  • 最后一步就会把就的链表和新的链表进行拆分处理,拆成两个新的链表。
    下面是代码,不知道为内存超限了,注意一点就是第一次copy的时候,tail指针的位置要落在原来的元素上,而不是copy了之后的元素上。
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
/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
RandomListNode* Clone(RandomListNode* pHead)
{
RandomListNode* realHead=new RandomListNode(-1);
realHead->next=pHead;
RandomListNode* prev=realHead;
RandomListNode* tail=pHead;
while(tail!=NULL){
RandomListNode* newNode=new RandomListNode(tail->label);
newNode->next=tail->next;
newNode->random=tail->random;
prev->next=newNode;
prev=tail->next;
tail=tail->next;
}

tail=pHead;
RandomListNode*copyNode=NULL;
while(tail!=NULL){
copyNode=tail->next;
copyNode->random=copyNode->random->next;
tail=tail->next->next;
}

prev=realHead;
tail=pHead;
while(tail!=NULL){
prev->next=tail->next;
prev=prev->next;
tail=tail->next->next;
}

return realHead->next;

}
};

判断一个单链表是否有环并找出相遇点

如何判断一个单链表中是否有环,有环的话,进入环的第一个节点,无环的话,返回空。判断单链表是否有环的操作还是挺容易的,但是找第一个节点的这个操作还是有点难,可以看之前的这个,还是死记住吧。。。关键是中间的那个方程的推导。

当然还是有简单思路的,如果没有空间复杂度的限制条件,可以采用hash表的思路进行求解,每次遍历一个元素,在hash表中将这个元素记录一下,key值可以是一个自增的index,value值可以是地址,之后如果在hash表中,发现了重复出现的元素,就说明其中有环,那么第一个重复出现的元素,也就是环开始的地方,这种方式相比于上一种,思路上是简洁明了的,实现上也是会简单许多的。

注意题目的多种解法。

稍微把之前blog中的算法做一下改动即可,前面的各种情况判断确实有点复杂,不确定重新写一次的话,还是否能够写对,前面在考虑链表长度为0和1的时候,已经考虑了许多特殊的情况。

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
class ChkLoop {  
public:
int chkLoop(ListNode* head, int adjust) {
ListNode *h1=head;
ListNode *h2=head;
bool cycle=false;
int flag=0;
if (head==NULL){
cycle = false;
flag=1;
}
if (h1!=NULL&&h1->next==h1){
cycle =true;
flag=1;
}
if (h1!=NULL&&h1->next==NULL){
cycle = false;
flag=1;
}
while(h1!=NULL&&h2!=NULL&&flag==0){
h1=h1->next;
if(h2->next!=NULL){
h2=h2->next->next;
}else{
break;
}
if(h1==h2){
cycle=true;
break;
}
}
if(cycle==false){
return -1;
}else{
h1=head;
while(h1!=h2){
h1=h1->next;
h2=h2->next;
}
}
return h1->val;
}
};

判断两个无环单链表是否相交

考研时候的场景真是历历在目啊。

  • 首先是遍历两个链表,得到它们的长度,m以及n,比如m>n,说明第一个链表比第二个多出m-n个节点。
  • 之后让指向第一个链表的指针向后走m-n步,这样两个链表就在同样的起点位置了。
  • 之后让指向两个链表的指针一起往后遍历,如果出现了公共的节点,说明两个链表在某个位置开始相交了。

当然还是有普通解法,就是类似上个题目一样,采用“万能的”hash表来实现,分别遍历两个链表,然后把其中的元素记录在hash表中,如果出现重复的,说明两个链表在这个位置开始相交了。如果一直没有出现重复的元素,说明两个链表不相交。

注意程序里面,最后一步的地方,先判断两个节点是否相同,然后再往下走,注意清楚逻辑顺序!

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
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class CheckIntersect {
int getLen(ListNode* head){
int len=0;
ListNode* tail=head;
while(tail!=NULL){
len=len+1;
tail=tail->next;
}
return len;
}
public:
bool chkIntersect(ListNode* headA, ListNode* headB) {
// write code here
int lena=getLen(headA);
int lenb=getLen(headB);
ListNode*taila=headA;
ListNode*tailb=headB;
int temp;
if(lena>lenb){
temp=lena-lenb;
while(temp--){
taila=taila->next;
}
}else{
temp=lenb-lena;
while(temp--){
tailb=tailb->next;
}
}

//move together
while(taila!=NULL&&tailb!=NULL){
if (taila==tailb){
return true;
}
taila=taila->next;
tailb=tailb->next;
}
return false;
}
};

如何判断两个有环的单链表是否相交

如何判断两个有环的单链表是否相交,相交的话,返回第一个相交的节点,不相交的话,返回空。

当然,万能的hash表还是可以解决这个题目的。

首先要明确的一个基本概念,什么样的情况叫做链表相交,实际上更准确的表述是说,两个链表,从某个节点开始之后,剩下的部分都开始重合了,不存才那种”X”形式的相交,因为根据链表的结构,不会有两个next指针,只能是类似”Y”形的这种情况。或者是Y形后面接一个环的形状,再或者是一个环,然后分出两个小枝,两个链表在环的不同节点位置入环。

更高效的思路,首先是判断两个链表的环的起始的节点,具体方法可以根据上面的题目中的思路,比如两个如环节点分别是head1与head2

  • 如果head1=head2,两个链表可能在入环之前就出现相交,这个时候按照上上题的方式,只不过遍历的终止节点为head1=head2
  • 如果head1!=head2 可能是两个有换的链表根本不相交,或者如环节点是大环上的两个节点,这个时候从head1开始遍历,如果在遍历过程中找到了head2,说明是第二种情况,返回head1或者是head2都是可以的,如果在遍历的过程中,没有找到head2,又回到了head1节点,说明两个环形链表是不相交的。
    没有在规定时间运行完??(需要把上一个题目的程序修改下,结束标志由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
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
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
*/
class ChkIntersection {

int getLen(ListNode* head,ListNode*common){
int len=0;
ListNode* tail=head;
while(tail!=common){
len=len+1;
tail=tail->next;
}
return len;
}
bool chkIntersect(ListNode* headA, ListNode* headB,ListNode*common) {
// write code here
int lena=getLen(headA,common);
int lenb=getLen(headB,common);
ListNode*taila=headA;
ListNode*tailb=headB;
int temp;
if(lena>lenb){
temp=lena-lenb;
while(temp--){
taila=taila->next;
}
}else{
temp=lenb-lena;
while(temp--){
tailb=tailb->next;
}
}

//move together
while(taila!=common&&tailb!=common){
if (taila==tailb){
return true;
}
taila=taila->next;
tailb=tailb->next;
}
return false;
}


ListNode* detectCycle(ListNode* head) {
ListNode *h1=head;
ListNode *h2=head;
bool cycle=false;
int flag=0;
if (head==NULL){
cycle = false;
flag=1;
}
if (h1!=NULL&&h1->next==h1){
cycle =true;
flag=1;
}
if (h1!=NULL&&h1->next==NULL){
cycle = false;
flag=1;
}
while(h1!=NULL&&h2!=NULL&&flag==0){
h1=h1->next;
if(h2->next!=NULL){
h2=h2->next->next;
}else{
break;
}
if(h1==h2){
cycle=true;
break;
}
}
if(cycle==false){
return NULL;
}else{
h1=head;
while(h1!=h2){
h1=h1->next;
h2=h2->next;
}
}
return h1;
}
public:
bool chkInter(ListNode* head1, ListNode* head2, int adjust0, int adjust1) {
// write code here
ListNode * pointA=detectCycle(head1);
ListNode * pointB=detectCycle(head2);
if (pointA==NULL||pointB==NULL){
return false;
}

if(pointA==pointB){
return chkIntersect(head1,head2,pointA);
}else{
ListNode*curr=pointA->next;
while(curr!=pointA){
if (curr==pointB){
return true;
}
}
return false;
}

}

};

判断两个单链表是否相交(综合题目)

给定两个单链表的头结点head1以及head2,如何判断两个链表是否相交?相交的话返回第一个相交的节点,不想交的话返回空。

这个题目的关键之处,是不确定两个链表是否为有环链表,还是无环链表。所以只要分类讨论即可,实际上是链表相交类题目的一个综合。

推荐文章