目录
一.反转链表
1.思路
2.代码实现
二.链表中倒数第k个节点
1.思路
2.代码实现
三.相交链表
1.思路
2.代码实现
四.环形链表
1.思路
2.代码实现
一.反转链表
1.思路
2.代码实现
struct ListNode {
int val;
struct ListNode *next;
};//链表结构
struct ListNode* reverseList(struct ListNode* head) {
if (head == NULL)
return NULL;//如果为空链表,则反转后还是为空
struct ListNode* n1, * n2, * n3;
n1 = NULL;
n2 = head;
n3 = head->next;
while (n2 != NULL)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
n3 = n3->next;//当n3为NULL时,不能对n3(即NULL)解引用
}
return n1;
}
二.链表中倒数第k个节点
1.思路
原理:slow和fast的距离拉开了k步,然后两个同时走,当fast走到空时,slow就是倒数第k个
2.代码实现
struct ListNode {
int val;
struct ListNode *next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* fast=pListHead, * slow = pListHead;
while (k--)
{
if (fast == NULL)
return NULL;//如果链表为空,或者k大于链表长度,返回空,防止对空指针的解引用
fast = fast->next;
}
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
三.相交链表
1.思路
思路1:暴力求解
方法:A链表中所有节点依次去B链表找一遍,若有与B链表中节点地址相同的,则为相交的起始节点
时间复杂度:n^2 (因为最坏情况下,A链表的每个节点都要在B链表遍历一遍)
思路2:优化,要求时间复杂度到O(N)
方法:
1.先判断是否相交
分别找到尾节点,尾节点地址相同就相交,尾节点地址不相同就不相交
2.再分别求出A链表和B链表的长度
长的先走差距步,两个链表再同时走,第一个相同节点的地址就是交点
2.代码实现
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
struct ListNode* curA=headA,*curB=headB;
int lenA=1,lenB=1;
while(curA->next)
{
lenA++;
curA=curA->next;
}
while(curB->next)
{
lenB++;
curB=curB->next;
}
//判断相交
if(curA!=curB)
return NULL;
int n=abs(lenA-lenB);
struct ListNode* longList=headA,*shortList=headB;
if(lenB>lenA)
{
longList=headB;
shortList=headA;
}
//长的先走差距步
while(n--)
{
longList=longList->next;
}
//同时走
while(longList!=shortList)
{
longList=longList->next;
shortList=shortList->next;
}
return longList;
}
四.环形链表
1.思路
带环链:表尾节点的next可以指向链表中任意节点(甚至可以指向自己)
定义快慢指针,fast,slow,都指向头节点,slow指针一次走一步,fast指针一次走两步
若链表无环,则快慢指针不可能相遇,返回false
若链表有环,则快慢指针一定相遇,当快慢指针相遇时表示链表有环,返回true
2.代码实现
struct ListNode {
int val;
struct ListNode *next;
};
bool hasCycle(struct ListNode* head)
{
struct ListNode* slow = head, * fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
return true;
}
}
return false;
}
若文章有任何问题,欢迎大家指正
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net