数据结构 链表OJ题

目录

一. 反转链表

 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;

}

若文章有任何问题，欢迎大家指正

精彩文章