不知不觉离上篇算法博客将近一个月时间，稍不留神时间就过去，学习算法是相当不容易的事
今天把链表相关题目练习完
1. 反转链表
分析：原始链表的尾部是新链表的头部，所以要currentHead->next = newHeader
时间复杂度：o(n)
空间复杂度：o(1)
void invertListNode(Node *header){
// 1.如果是空或者如果只有一个，直接return
if(header == NULL || header->next == NULL){
return;
}
// 2.开始遍历，将新下一个结点放在头结点的前边
Node *NewHeaderNode = NULL;
Node *currentHeadNode = header;
while (currentHeadNode != NULL) {
// 1.取当前头结点
Node *tempNode = currentHeadNode;
// 2.当前结点的尾部指向新链表的头部
tempNode->next = NewHeaderNode;
// 3. 当前结点后移
currentHeadNode = currentHeadNode->next;
// 4. 新头结点赋值
NewHeaderNode = tempNode;
}
}
2. 倒序第k个结点
分析：若先遍历到尾部，然后再来一个头指针遍历一次，需要时间复杂度o(n+k)，可以用两个指针一前一后操作，先让头指针先遍历k个点，然后同时开始操作，第一个指针遍历到尾部，第二个指针的位置就是了
时间复杂度:o(n)
注意：判断链表的长度是否比k大
Node *lastKNode(Node *header, int k){
if(k < 0 || header == NULL) return NULL;
// 1.先遍历到第k个结点
Node *tempHeader = header;
while (tempHeader && k > 0) {
k--;
tempHeader = tempHeader->next;
}
if(k > 0) return NULL;
// 2.再来一个指针从头遍历，第一个遍历完毕，第二个就是
Node *tempHeader2 = header;
while (tempHeader) {
tempHeader = tempHeader->next;
tempHeader2 = tempHeader2->next;
}
return tempHeader2;
}
3. 中间结点
分析：这个叫快慢指针，跟上题的思路类似，快指针一次遍历两个结点，快指针走到头，慢指针所指的位置就是
注意：判断链表的长度是0、1、2
Node *middleNode(Node *header){
// 1.合法性判断
if(header == NULL) return NULL;
if(header->next) return header;
if(header->next->next) return header;
// 2.使用快慢指针
Node *before = header;
Node *behind = header;
while (before->next) { //如果快指针走到头，遍历结束
before = before->next;
behind = behind->next;
if(before){
before = before->next;
}
}
return behind;
}
4.合并两个有序单链表
分析：从两个链表的头部开始，新链表的当前节点谁得大取谁得
时间复杂度：o(max(len1,len2))
空间复杂度：o(1)
Node * mergeTwoSortList(Node *header1, Node *header2){
// 1.判断
if(header1 == NULL) return header2;
if(header2 == NULL) return header1;
// 2.准备合并，先找第一个节点，要不然还得在while循环中判断；所以单拿出来操作
Node *newHeader = NULL;
if(header1->value < header2->value){
newHeader = header1;
header1 = header1->next;
}else if(header1->value > header2->value){
newHeader = header2;
header2 = header2->next;
}else{
newHeader = header1;
newHeader->next = header2;
header1 = header1->next;
header2 = header2->next;
}
Node *tempNode = newHeader;
// 3.开始合并
while (header1->next && header2->next) {
if(header1->value < header2->value){
tempNode->next = header1;
tempNode = tempNode->next;
header1 = header1->next;
}else if(header1->value > header2->value){
tempNode->next = header2;
tempNode = tempNode->next;
header2 = header2 -> next;
}else{
// 新链表指向header1结点
tempNode->next = header1;
// header1下移
header1 = header1->next;
// 新链表头指针下移
tempNode = tempNode->next;
// 同上，操作header2头结点
tempNode->next = header2;
header2 = header2->next;
tempNode = tempNode->next;
}
}
// 4. 合并剩余的部分
if(header1){
tempNode->next = header1;
}
if(header2){
tempNode->next = header2;
}
return newHeader;
}
5. 链表有环
思路：说明链表永远遍历不完，那么可以用快慢指针操作，一个指针走一步，一个走两步，在某一个时刻两个指针必然指向同一个值
时间复杂度：o(n)
空间复杂度：o(1)
bool nodeHasCircle(Node *header){
if(header == NULL) return false;
Node *before = header;
Node *behind = header;
while (before) {
before = before->next;
if(before){
before = before->next;
}
behind = behind->next;
if(before == behind) return true;
}
return false;
}
6. 链表交叉
思路：
- 将第二个链表头结点连接在第一个结点尾部，若相交则新链表必然有环，可以用上方有环操作判断
时间复杂度：o(len2)
bool nodeCross(Node *node1,Node *node2){
// 1.合法判断
if(node1 == NULL || node2 == NULL) return false;
// 3. 将第二个链表指向第一个连标点尾部
Node *header1 = node1;
while (header1->next) {
header1 = header1->next;
}
header1->next = node2;
return nodeHasCircle(node2);
}
- 若两个链表相交，则交点之后的结点是两个链表共有的，换句话说两个链表的尾结点肯定是同一个，则：分别遍历两个链表到尾部，若尾部相等则相交
时间复杂度：o(len1+len2)
bool nodeCross(Node *node1,Node *node2){
// 1.合法判断
if(node1 == NULL || node2 == NULL) return false;
// 2.分别遍历到尾部，比较尾部是否相等
Node *header1 = node1;
Node *header2 = node2;
while (header1->next) { //判断尾部
header1 = header1->next;
}
while (header2->next) {
header2 = header2->next;
}
if(header1 == header2){
return true;
}
}
- 求链表交点
分析：由于两个链表相交，则从交点到尾部都相等；链表的长度之差为：len1-len2 = k，则长链表先走k部之后，再同时走，必然相遇
时间复杂度：0(len1+len2+k+2*n)，各自遍历求长度复杂度分别为o(len1)、o(len2)，然后长链表先走k步，再各自走n步,总共就是这么多复杂度
空间复杂度：o(1)
Node *crossNode(Node *node1,Node *node2){
if(node1 == NULL || node2 == NULL) return NULL;
// 1.计算长度
int len1 = 0;
int len2 = 0;
Node *header1 = node1;
Node *header2 = node2;
while (header1) {
header1 = header1->next;
len1++;
}
while (header2) {
header2 = header2->next;
len2++;
}
// 长度为k
int k = len2>len1? len2-len1:len1-len2;
// 2.分情况遍历
if(len2 > len1){
// 2.1 长链表先走k部
while (k > 0) {
node2 = node2->next;
k--;
}
// 2.2 两个链表同时走，啥时候相等啥时候就是交点
while (node1 && node2) {
if(node1 == node2){
return node1;
}
node2 = node2->next;
node1 = node1->next;
}
}else{
while (k > 0) {
node1 = node1->next;
k--;
}
while (node1 && node2) {
if(node1 == node2){
return node2;
}
node2 = node2->next;
node1 = node1->next;
}
}
return NULL;
}
- 求链表环入口
涉及一个公式推导，有点儿烦躁！主要我没带笔，只能用脑子想，借笔也没借到，抬头一看咖啡馆里有个用pc玩穿越火线的，立刻回想起大一的日子~
思路：先推导公式：a = (n-1)c+(c-x)[推导过程可以参考下文章，c表示环的长度]，由推导公式可知，若两个指针p1,p2分别从头结点和相遇点同时移动，且速度相等，则p1移动到入口点时，p1移动了a距离，p2移动了a=(n-1)c+(c-x)=nc-x距离，也是入口点(相当于绕了n圈，然后倒退了x距离，由下图可知正好也是入口点)，那么就找到了这个入口点
参考 判断链表是否有环，环的入口以及环的长度
image
Node *circleStartNode(Node *header){
if(header == NULL) return NULL;
// 1.找到相遇点
Node *before = header;
Node *behind = header;
BOOL flag = false;//标记是否有环
while (before) {
before = before->next;
if(before){
before = before->next;
}
behind = behind->next;
if(before == behind){
flag = true;
break;
}
}
// 无环，直接返回
if(flag == false) return NULL;
// 2.定义两个指针，再次遍历
Node *startNode = header;
Node *meetNode = before;
while (startNode) {
//如果两个结点相等，就是要找的入口点
if(startNode == meetNode){
return startNode;
}
startNode = startNode->next;
meetNode = meetNode->next;
}
return NULL;
}
网友评论