引导
链表是我们工作和面试的中常常会遇到的知识点，只有长时间的练习和思考才能游刃有余。故总结以下几个比较经典的链表题和对应的代码，进行参考。
链表的反转
思路：
- 将链表遍历，将每个节点拷贝一份，之后再将所有的节点反向链接。该方法简单，但是我并不喜欢。因为空间复杂度为O(n),时间复杂度也为O(n).
- 利用递归，将先遍历到最后节点，再返回，将每个节点的指向上一个节点。头节点指向null。
| #include
typedef struct node{
int num;
struct node * next;
}Node;
int insertnode(Node* head,Node* newNode)
{
if(head == NULL)
{
printf("head is null,insert fail\n");
return -1;
}
Node* temp = head;
while(temp->next!= NULL)
{
temp = temp->next;
}
temp->next = newNode;
return 0;
}
int print_list(Node* head)
{
while(head!=NULL)
{
printf("%d\n",head->num);
head = head->next;
}
return 0;
}
Node* rollback(Node* head)
{
Node* temp = head->next;
Node* newhead = NULL;
if(temp != NULL)
{
newhead = rollback(temp);
}
else
{
return head;
}
temp->next = head;
head->next = NULL;
return newhead;
}
int main()
{
Node * head = (Node*)malloc(sizeof(Node));
head->num = 1;
head->next = NULL;
int i = 0;
for(i = 2 ; i < 5 ; i ++)
{
Node * NewNode = (Node*)malloc(sizeof(Node));
NewNode->num = i;
NewNode->next = NULL;
insertnode(head,NewNode);
}
print_list(head);
Node* Newhead = rollback(head);
print_list(Newhead);
return 0;
} |
单向链表中环的检测
该题，我觉得可以拓展到以下三个问题：
- 1.检测链表中是否存在环?
- 2.能够求出环的长度?
- 3.能否求出起始点到环入口的长度?
检测链表中是否存在环
思路：
- 使用快慢指针，快指针指向NULL时，则不存在环；若快指针和慢指针重合，则说明有环
| #include
typedef struct node{
int num;
struct node * next;
}Node;
int insertnode(Node* head,Node* newNode)
{
if(head == NULL)
{
printf("head is null,insert fail\n");
return -1;
}
Node* temp = head;
while(temp->next!= NULL)
{
temp = temp->next;
}
temp->next = newNode;
return 0;
}
int print_list(Node* head)
{
while(head!=NULL)
{
sleep(1);
printf("%d\n",head->num);
head = head->next;
}
return 0;
}
int ring_check(Node* head)
{
int result = -1;
Node* fast=head;
Node* slow=head;
while(fast != NULL)
{
if(slow->next != NULL)
slow = slow->next;
if(fast->next != NULL && fast->next->next != NULL)
fast = fast->next->next;
else
break;
if(slow == fast)
{
printf("number = %d\n",slow->num);
result = 1;
break;
}
}
return result;
}
int main()
{
Node * head = (Node*)malloc(sizeof(Node));
head->num = 1;
head->next = NULL;
Node * temp = NULL;
int i = 0;
for(i = 2 ; i < 2 ; i ++)
{
Node * NewNode = (Node*)malloc(sizeof(Node));
NewNode->num = i;
NewNode->next = NULL;
insertnode(head,NewNode);
if(i == 14)/
*决定环的入口点*
/
{
temp = NewNode;
}
if(i == 19)
{
NewNode->next = temp;
}
}
int resulte = ring_check(head);
//print_list(head);
if(resulte == 1)
{
printf("list exist ring\n");
}
else
{
printf("list don't exit ring\n");
}
return 0;
} |
求出环的长度
思路：
- 建立在问题一的基础之上：
- 当第一次相遇之后，说明该链表存在环。
- 而快慢指针从一个环中同一点进行移动，下一次相遇就是链表的长度。
| int ring_len(Node* head)
{
int first = -1;
int len = 0;
Node* fast=head;
Node* slow=head;
while(fast != NULL)
{
if(slow->next != NULL)
slow = slow->next;
if(fast->next != NULL && fast->next->next != NULL)
fast = fast->next->next;
else
break;
if(first == 1)
len ++;
if(slow == fast)
{
printf("number = %d\n",slow->num);
if(first == -1)
{
first = 1;
}
else
break;
}
}
return len;
} |
计算头节点到入口点的距离
思路：
依据：快指针和慢指针相遇时，慢指针肯定还没有超过整个链表长度。而快指针应该是超过链表加上nr（n,表示正整数，r表示环的长度）
现做这样的假设：
链表的整个长度是L
头节点到入口点的距离为a
第一次相遇点距离入口点为X，并走了s步
得到以下公式：
2s -s = nr
x+a = s
可以得到a= (n-1)r + (r-x)
其中r-x表示相遇点到入口点的距离。
故：从head节点，第一次相遇节点分别出发。再次相遇肯定是入口点。
| Node* ring_meet(Node* head)
{
Node* resulte = NULL;
Node* fast=head;
Node* slow=head;
while(fast != NULL)
{
if(slow->next != NULL)
slow = slow->next;
if(fast->next != NULL && fast->next->next != NULL)
fast = fast->next->next;
else
return resulte;
if(slow == fast)
{
printf("number = %d\n",slow->num);
break;
}
}
resulte = head;
int len = 0;
while(resulte != slow)
{
resulte= resulte->next;
slow = slow->next;
len++;
}
printf("len = %d\n",len);
return resulte;
} |
如何判断两个链表是否相交
该问题其实就是环检测的变种。只要将其中一个链表尾节点指向头节点。再检测另一条链表中是否存在环即可。
两个有序的链表合并
思路：
遍历其中一个链表，将节点与另一链表进行比较，进行插入。
| Node * list_merge(Node*L1 , Node*L2)
{
Node * head= (Node*)malloc(sizeof(Node));
Node* cur = head;
while(L1 != NULL && L2 != NULL)
{
if(L1->num <= L2->num )
{
cur->next = L1;
L1 = L1->next;
}
else
{
cur->next = L2;
L2 = L2->next;
}
cur=cur->next;
}
if(L1 == NULL)
{
cur->next=L2;
}
if(L2 == NULL)
{
cur->next=L1;
}
return head->next;
} |
删除链表中指定节点
思路：
- 遍历链表，当遇到节点相同的，便删除对应节点。这样的事件复杂度为O(n)
- 将节点的下一个节点赋值为本节点，之后指向node->next->next;这个思路的时间复杂度是O(1)。但是你需要考虑节点的位置；
- 在链表头
- 在链表尾
- 在链表中间
| int delete_node(Node* head,Node* delete)
{
if(delete==NULL )
{
return 0;
}
if(delete->next == NULL)
{
/
*last node*
/
while(head->next != delete)
{
head=head->next;
}
head->next = NULL;
free(delete);
return 0;
}
delete->num = delete->next->num;
Node * temp = delete->next;
delete->next = delete->next->next;
free(temp);
return 0;
}
平均复杂度为O(1)。 |
求链表中的中间节点
思路:（当链表长度为偶数，取相邻两个节点的第一个）
- 遍历链表，找到尾节点。并记录链表长度。再从头结点遍历，达到中间节点即可。这种方式事件复杂度为O(n),空间复杂度O(1)。但感觉太low了，并不喜欢。
- 使用快慢指针，当快指针达到尾节点时，慢节指针肯定是在中间节点
| Node* mid_node(Node* head)
{
if(head == NULL)
{
return NULL;
}
Node* fast=head;
Node* slow = head;
while(fast->next != NULL && fast->next->next != NULL)
{
fast=fast->next->next;
slow=slow->next;
}
return slow;
} |
约瑟夫问题
约瑟夫问题，是我偶然看到的一个算法题。感觉很有意思，就记录下来了。
故事：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人抓到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从。首先从一个人开始，越过k-2个人（因为第一个人已经被越过），并杀掉第k个人。接着，再越过k-1个人，并杀掉第k个人。这个过程沿着圆圈一直进行，直到最终只剩下一个人留下，这个人就可以继续活着。问题是，给定了和，一开始要站在什么地方才能避免被处决？Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
该问题拓展很多，这里我给出的问题，有100个人，每数到3，就剔除，输出剔除顺序。
例如： 1，2，3，4，5，6
输出：3，6，4，2，5，1
思路：
实现起来应该是很简单的，就是有N个节点的环，从头节点开始，依次数数，当数到3时，就将节点删除，一直重复到只有一个节点。
| int Joseph(Node* head)
{
int i = 1;
if(head ==NULL)
{
printf("list is empty\n");
}
while(head->next != head)
{
i++;
if(i%3 == 0)
{
i=1;
Node* temp = head->next;
head->next = head->next->next;
printf("%d\n",temp->num);
free(temp);
}
head=head->next;
}
printf("last is %d\n",head->num);
} |