引言
一些经典单链表OJ题目的总结和题目讲解
1.判断链表中是否有环
- 具体思路
分为两种情况，无环的情况很好判断，只要遍历链表结束则可判断
但是如果是环形链表的话，如果一直遍历则会无限遍历下去，这里我们可以采取快慢指针的方式结束遍历数组
- 具体实现方式如下
typedef struct ListNode Node;
bool hasCycle(struct ListNode *head) {
Node* fast = head;
Node* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
return true;
}
}
return false;
}2.找到两个单链表的交点
- 具体思路
先找到哪个是长指针，哪个是短指针，计算他们长度的差值，然后移动长指针与短指针的长度一样长，再一起遍历，就可以找到交点
- 具体实现如下：
typedef struct ListNode Node;
//计算链表长度
int length(Node* head)
{
Node* root = head;
int i = 0;
while(root)
{
i++;
root = root->next;
}
return i;
}
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
//计算两个链表长度
int Short = length(headA);
Node* sho = headA;
int Long = length(headB);
Node* lon = headB;
if(Short > Long)
{
int k = Short;
Short = Long;
Long = k;
sho = headB;
lon = headA;
}
int n = Long - Short;
for(int i = 0; i < n; i++)
{
lon = lon->next;
}
while(lon != sho)
{
lon = lon->next;
sho = sho->next;
}
return lon;
}坑：
1.遍历完两个链表后，记得重新赋值长指针跟短指针的值，因为这时两个指针已经指向空指针了(可有可无)
2.注意循环条件不要写反了！
技巧：
这里长短指针的赋值可以采用假设法（具体实现看解析）
3.找到环形链表中进入环的节点
题目链接：142. 环形链表 II – 力扣（LeetCode）
- 方法一
先用问题一的方法找到fast指针跟slow指针相遇的节点，然后在用新的指针定义头节点，两个指针同时向前走，相交的地方就是进入环的节点，具体实现如下
typedef struct ListNode Node;
struct ListNode *detectCycle(struct ListNode *head) {
Node* fast = head;
Node* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
break;
}
}
if(fast == NULL || fast->next == NULL)
{
return NULL;
}
Node* cur1 = head;
Node* cur2 = fast;
while(cur1 != cur2)
{
cur1 = cur1->next;
cur2 = cur2->next;
}
return cur1;
}原理实现如下：
- 方法二
可以转化为两个单链表，找他们的相交节点，具体实现如下：
typedef struct ListNode ListNode;
struct ListNode *detectCycle(struct ListNode *head) {
//先找到快慢指针的相交点
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
break;
}
}
if(fast == NULL || fast->next == NULL)
{
return NULL;
}
//可以采用找两个链表相交的方式
//先对相交节点的next节点置空
ListNode* next = fast->next;
fast->next = NULL;
ListNode* st = next;
ListNode* cur = head;
int n1 = 0;
int n2 = 0;
while(st)
{
st = st->next;
n1++;
}
while(cur)
{
cur = cur->next;
n2++;
}
ListNode* Short = next;
ListNode* Long = head;
if(n1 > n2)
{
Short = head;
Long = next;
}
int k = abs(n1 - n2);
while(k--)
{
Long = Long->next;
}
while(Long != Short)
{
Long = Long->next;
Short = Short->next;
}
return Short;
}需要注意点的坑：
要先把next的指针存好，要不然找到的next指针就是空指针了
4.链表的回文结构
题目链接：链表的回文结构_牛客题霸_牛客网
- 前提条件
要先学会逆转链表和找到中间节点，题目链接：206. 反转链表 – 力扣（LeetCode） 876. 链表的中间结点 – 力扣（LeetCode）
- 解题思路：
首先我们要找到中间节点，然后将后半部分链表逆转，就可以把前半部分和后半部分的数值进行比较
为什么要这样做呢？因为在单链表中，要找到前一个节点是很困难的，所以我们要逆转数组
- 具体实现如下：
typedef struct ListNode ListNode;
//找到中间节点
ListNode* MidFind(ListNode* head)
{
if(head == NULL)
{
return NULL;
}
ListNode* fast = head;
ListNode* slow = head;
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//反转链表
ListNode* Retrun(ListNode* head)
{
if(head == NULL)
{
return NULL;
}
ListNode* n1 = NULL;
ListNode* n2 = head;
ListNode* n3 = head->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
{
ListNode* next = n3->next;
n3 = next;
}
}
return n1;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
ListNode* mid = MidFind(A);
mid = Retrun(mid);
while(mid)
{
if(mid->val != A->val)
{
return false;
}
mid = mid->next;
A = A->next;
}
return true;
}
};- 一些难以明白的地方
当是节点数量奇数个时，例如1 2 3 2 1，那么逆转后就是 1 2 1 2 3，你可能会疑惑，如果比完1 2后，3不就会出错了吗，但其实不是这样的，我们并没有改掉第一个2节点的next指针，所以它仍然指向的还是3这个节点，比较值的时候是可以匹配上的，所以我们不需要多考虑这种情况
5.随机链表的复制（综合）
题目链接：138. 随机链表的复制 – 力扣（LeetCode）
- 具体实现思路：
1.分别将前一个节点插入前后两个节点当中（方便random的寻找）
2.给random赋值，创建头指针（phaed）跟尾指针（ptail），random的寻找格式如下：
ptail->random = cur->random->next;
这是因为我们之前在每个节点后创建了一个与它们值相同的节点，所以random指向的节点的下一个节点就是我们要链接的random节点
3.链接新的节点
4.返回头指针phead结束
具体实现如下：
typedef struct Node Node;
//创建新节点
Node* Create(int x)
{
Node* new = (Node*)malloc(sizeof(Node));
new->val = x;
new->next = NULL;
return new;
}
struct Node* copyRandomList(struct Node* head) {
Node* cur = head;
//插入新链表
while(cur)
{
Node* new = Create(cur->val);
new->next = cur->next;
Node* next = cur->next;
cur->next = new;
cur = next;
}
//给random赋值
cur = head;
while(cur)
{
Node* copy = cur->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;//注意这里的是cur的random地址，因为copy的random未赋值
}
cur = copy->next;
}
//链接链表，并且恢复原链表
Node* phead = NULL;
Node* ptail = NULL;
cur = head;
while(cur)
{
if(phead == NULL)
{
phead = ptail = cur->next;
}
else{
ptail->next = cur->next;
ptail = ptail->next;
}
cur->next = ptail->next;
cur = cur->next;
}
return phead;
}- 具体实现可能会的坑（反正我踩了）：
1.注意赋值的时候=不要写成==了，要不然不仅不报错还会出错
2.链接链表和给random赋值最好在两个while循环中进行，不要一起做，要不然容易出问题
3.给random赋值的时候要记得判空，如果random为空，那random->next就是野指针，是无法赋值的
4.进行赋值是cur的random，不要写错了，复制的节点的random此时还没有赋值，是找不到的
总结
如果你已经能很熟练的掌握上述几个单链表的OJ题目，那你的单链表的基本功已经掌握的很好了，恭喜恭喜，今后也要继续加油！
评论（0）
暂无评论