链表OJ题
1. 链表的回文布局https://img-blog.csdnimg.cn/direct/d7860bcff3654573b33339af17e0afa1.png
由于单链表不能从后往前找节点，以是我们先找到中间节点，然后逆置，最后进行比力。
#include <stdio.h>
#include <stdbool.h>
typedef struct ListNode
{
int val;
struct ListNode* next;
}ListNode;
struct ListNode* middleNode(struct ListNode* head)
{
ListNode* slow, * fast;
slow = fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
struct ListNode* reverseList(struct ListNode* head)
{
if (NULL == head)
{
return head;
}
ListNode* n1, * n2, * n3;
n1 = NULL, n2 = head, n3 = head->next;
while (n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if (n3)
{
n3 = n3->next;
}
}
return n1;
}
bool chkPalindrome(ListNode* A)
{
ListNode* mid = middleNode(A);
ListNode* rmid = reverseList(mid);
while (A && rmid)
{
if (A->val != rmid->val)
{
return false;
}
A = A->next;
rmid = rmid->next;
}
return true;
}
2. 相交链表
https://img-blog.csdnimg.cn/direct/1e1bd3b6eee9447b9088388bcb806c44.png
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA;
struct ListNode* curB = headB;
int lenA = 0;
while (curA->next)
{
++lenA;
curA = curA->next;
}
int lenB = 0;
while (curB->next)
{
++lenB;
curB = curB->next;
}
//不相交
if (curA != curB)
{
return NULL;
}
int gap = abs(lenA - lenB);
//因为我们不知道A长还是B长，所以我们要用假设法，先假设A长，如果不对，再调换一下就行
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if (lenB > lenA)
{
longList = headB;
shortList = headA;
}
//让长的先走gap步
while (gap--)
{
longList = longList->next;
}
//再同时走，找交点
while (longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
3. 链表中倒数第k个结点
https://img-blog.csdnimg.cn/direct/f483ba401d0f42c1b0572f884332632f.png
思路2：
#include <stdio.h>
struct ListNode
{
int val;
struct ListNoe* next;
};
struct ListNode* FindKthToTail(struct ListNode* pListHead, int k)
{
struct ListNode* slow = pListHead, * fast = pListHead;
//fast先走k步
while (k--)
{
//k还没有减到0，链表已经空了，说明k大于链表的长度
if (NULL == fast)
{
return NULL;
}
fast = fast->next;
}
//slow和fast同时走，fast走到空，slow就是倒数第k个
while (fast)
{
slow = slow->next;
fast = fast->next;
}
return slow;
}
4. 环形链表
https://img-blog.csdnimg.cn/direct/ff349c8879954016bb8e6becee5482a6.png
https://img-blog.csdnimg.cn/direct/fd5dbf3b874e4806a99634673b58f823.png
#include <stdbool.h>
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;
}
5. 环形链表 II
找入环点：
https://img-blog.csdnimg.cn/direct/25c30db303544c1082f96d797389fdd4.png
法一：
#include <stdio.h>
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head, * fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
while (meet != head)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
法二：
#include <stdio.h>
#include <stdlib.h>
struct ListNode
{
int val;
struct ListNode* next;
};
struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB)
{
struct ListNode* curA = headA;
struct ListNode* curB = headB;
int lenA = 0;
while (curA->next)
{
++lenA;
curA = curA->next;
}
int lenB = 0;
while (curB->next)
{
++lenB;
curB = curB->next;
}
//不相交
if (curA != curB)
{
return NULL;
}
int gap = abs(lenA - lenB);
struct ListNode* longList = headA;
struct ListNode* shortList = headB;
if (lenB > lenA)
{
longList = headB;
shortList = headA;
}
//让长的先走gap步
while (gap--)
{
longList = longList->next;
}
//再同时走，找交点
while (longList != shortList)
{
longList = longList->next;
shortList = shortList->next;
}
return longList;
}
struct ListNode* detectCycle(struct ListNode* head)
{
struct ListNode* slow = head, * fast = head;
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if (slow == fast)
{
struct ListNode* meet = slow;
struct ListNode* headx = meet->next;
meet->next = NULL;
return getIntersectionNode(head, headx);
}
}
return NULL;
}
6. 随机链表的复制
https://img-blog.csdnimg.cn/direct/5691487aee14483d9f06c7cdf4e8ac59.png
写代码的时候建议一边画细图，一边写：
https://img-blog.csdnimg.cn/direct/1a9b50864efa4901939adbd82c279dc0.png
#include <stdio.h>
#include <stdlib.h>
struct Node
{
int val;
struct Node *next;
struct Node *random;
};
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur = head;
//拷贝节点插入原节点的后面
while (cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
//插入
copy->next = cur->next;
cur->next = copy;
//迭代
cur = cur->next->next;
}
//控制拷贝节点的random
cur = head;
while (cur)
{
struct Node* copy = cur->next;
if (NULL == cur->random)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
//迭代
cur = cur->next->next;
}
//把copy节点解下来，链接成新链表
struct Node* copyhead = NULL, * tail = NULL;
cur = head;
while (cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
//尾插
if (NULL == tail)
{
copyhead = tail = copy;
}
else
{
tail->next = copy;
tail = tail->next;
}
cur->next = next;
cur = next;
}
return copyhead;
}
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]