# 链表练习题-2

https://developer.aliyun.com/article/1498105

## 相交链表

A中的每个节点的地址在B链表都找一遍,然后比较,时间复杂度是O(n^2)

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{

while(taila)
{
while(tailb)
{
if(taila == tailb)
{
return tailb;
}
tailb = tailb->next;
}
taila = taila->next;
}
return NULL;
}


struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
return NULL;
int conut1 =1;
int conut2 =1;
//找出尾节点,随便算出cah
while(tail1->next)
{
tail1 = tail1->next;
conut1++;
}
while(tail2->next)
{
tail2 = tail2->next;
conut2++;
}
if(!(tail1 == tail2))
return NULL;
int i = 0;
for (i = 0; i <abs(conut1 -conut2);i++)
{
maxh = maxh->next;
}
while(minh)
{
if(maxh == minh)
{
return maxh;
}
maxh = maxh->next;
minh = minh->next;
}
return NULL;
}


## 环形链表

bool hasCycle(struct ListNode *head)
{
int a = 10002;
while(tail)
{
if(a==0)
return true;
a--;
tail = tail->next;

}
return false;
}


slow一次走一步，fast一次走两步,当slow刚刚进入到环里面时

fast和slow的距离就是X,转换成fast追逐slow

v1 t - v2t = X, t = x/(v1 - v2)


{
while(fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
return true;
}
return false;
}


## 环形链表 II

slow一次走一步，fast一次走两步,当slow刚刚进入到环里面时,fast和slow的距离就是X,转换成slow和fast在入环点的经过x的长度相遇,c为环的长度

struct ListNode *detectCycle(struct ListNode *head)
{
return NULL;
//找出相遇点
while (prev && prev->next)
{

tail = tail->next;
prev = prev->next ->next;
//找出相遇点
if(tail == prev)
{ //开始两个指针走
while(tail != prev)
{
tail = tail->next;
prev = prev->next;
}
return tail;
}
}

return NULL;
}


 struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
return NULL;
int conut1 =1;
int conut2 =1;
//找出尾节点,随便算出cah
while(tail1->next)
{
tail1 = tail1->next;
conut1++;
}
while(tail2->next)
{
tail2 = tail2->next;
conut2++;
}
if(!(tail1 == tail2))
return NULL;
int i = 0;
for (i = 0; i <abs(conut1 -conut2);i++)
{
maxh = maxh->next;
}
while(minh)
{
if(maxh == minh)
{
return maxh;
}
maxh = maxh->next;
minh = minh->next;
}
return NULL;
}
{
return NULL;
//找出相遇点
while (prev && prev->next)
{

tail = tail->next;
prev = prev->next ->next;
//找出相遇点
if(tail == prev)
{ //开始两个指针走
struct ListNode*p = prev->next;
prev->next = NULL;
p = getIntersectionNode(tail, p);
if(p)
return p;
}
}

return NULL;
}


## 合并两个有序链表

struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2)
{
if(list1 == NULL)
return list2;
if(list2 == NULL)
return list1;
struct ListNode*newnode =NULL;
struct ListNode*prev =NULL;
struct ListNode* tail1 = list1;
struct ListNode* tail2 = list2;
while(tail1 && tail2)
{
if(tail1->val < tail2->val)
{
if(prev == NULL)
{
newnode = tail1;
prev = tail1;
tail1 = tail1->next;
}
else
{
prev->next = tail1;
prev = prev->next;
tail1 = tail1->next;
}
}
else
{
if(prev == NULL)
{
newnode = tail2;
prev = tail2;
tail2 = tail2->next;
}
else
{
prev->next = tail2;
prev = prev->next;
tail2 = tail2->next;
}
}
}
if(tail1)
prev->next = tail1;
if(tail2)
prev->next = tail2;
return newnode;

// if(list1 == NULL)
//     return list2;
// if(list2 == NULL)
//     return list1;
// //哨兵位
// struct ListNode *newnode = (struct ListNode*)malloc(sizeof(struct ListNode));
// struct ListNode* tail1 = list1;
// struct ListNode* tail2 = list2;
// struct ListNode* prev = newnode;
// while(tail1 && tail2)
// {
//     if(tail1->val > tail2->val)
//     {
//         prev->next = tail2;
//         tail2 = tail2->next;
//     }
//     else
//     {
//         prev->next = tail1;
//         tail1 = tail1->next;
//     }
//     prev = prev->next;
// }
// if(tail1)
//     prev->next = tail1;
// if(tail2)
//     prev->next = tail2;
// struct ListNode *ph = newnode->next;
// free(newnode);
// return ph;
}


## 链表的回文结构

class PalindromeList {
public:
{
return true;
//双指针速度差法

while(fast && fast->next)
{
fast = fast ->next ->next;
slow = slow->next;
}
//slow为中间节点
//后部分反转

struct ListNode *n1 = NULL;
struct ListNode *n2 = slow;
struct ListNode *n3 = slow->next;
while(n2)
{
n2->next = n1;
n1 = n2;
n2 = n3;
if(n3)
n3 = n3->next;
}

//fast为第二个链表头节点地址
fast = n1;
while(slow && fast)
{
if(slow->val != fast->val)
{
return false;
}
slow = slow->next;
fast = fast->next;

}
return true;

//双指针比较
}
};


## 随机链表的复制

struct Node* copyRandomList(struct Node* head)
{
return NULL;
while(cur)
{
//创建节点
struct Node *copy = (struct Node *)malloc(sizeof(struct Node));
copy->val = cur->val;
struct Node *cp = cur->next;
cur->next = copy;
copy->next = cp;
cur = cp;
}
//开始指向random

while(cur)
{
struct Node *cp = cur->next;
if(cur->random)
cp->random = cur->random->next;
else
cp->random = NULL;
cur = cur->next->next;

}
//创建空链表,然后尾插
//创建哨兵位
struct Node *newnode = (struct Node *)malloc(sizeof(struct Node));
struct Node *tail = newnode;
//开始尾插
while(cur)
{
struct Node *new = cur->next;
tail->next = new;
tail = tail->next;
cur = new->next;
}

struct Node *p = newnode->next;
free(newnode);
return p;
}


|
2月前
|

20 0
|
2月前
|

17 1
|
2月前
【链表之练习题】
【链表之练习题】
31 1
|
2月前
【无头双向链表和链表练习题2】
【无头双向链表和链表练习题2】
27 0
|
9月前
|

37 1
|
2月前
【移除链表元素】LeetCode第203题讲解
【移除链表元素】LeetCode第203题讲解
30 0
|
1月前
|

LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
LeetCode力扣第114题：多种算法实现 将二叉树展开为链表
18 0
|
1月前
|

LeetCode 题目 86：分隔链表
LeetCode 题目 86：分隔链表
21 2
|
1月前
|

【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
【经典算法】Leetcode 141. 环形链表(Java/C/Python3实现含注释说明,Easy)
14 2
|
2月前
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点.
＜数据结构＞五道LeetCode链表题分析.环形链表，反转链表，合并链表，找中间节点
30 1