# LeetCode每日一刷 — 手撕单链表习题（2）

1、链表的回文结构

2、相交链表

3、复制带随机指针的链表

### 1、链表的回文结构

• 链接直达：

• 题目：

•  思路：

•  代码如下：
``````class PalindromeList {
public:
//第一步：找到中间节点
struct ListNode* middleNode(struct ListNode* head) {
while (fast && fast->next)
{
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
//第二部：逆置从中间节点开始往后的数据，并返回新的头节点
struct ListNode* reverseList(struct ListNode* head) {
{
return NULL;
}
struct ListNode* n3 = NULL;
while (n1)
{
n1->next = n3;
n3 = n1;
n1 = n2;
if (n2)
{
n2 = n2->next;
}
}
return n3;
}

bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid = middleNode(A);
{
{
A = A->next;
}
else
{
return false;
}
}
return true;
}
};``````

### 2、相交链表

• 链接直达：

• 题目：

• 思路：

• 代码如下：
``````struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
int lenA = 0;
int lenB = 0;
//1、判断是否相交
while (cur1->next)
{
cur1 = cur1->next;
lenA++;
}
while (cur2->next)
{
cur2 = cur2->next;
lenB++;
}
//若相交，进入if判断
if (cur1 == cur2)
{
if (lenA > lenB)
{
}
int num = abs(lenA - lenB);
//让长的链表先走差距步
while (num--)
{
longList = longList->next;
}
while (shortList && longList)
{
if (shortList == longList)
{
return shortList;
}
//此时两链表一起走
else
{
shortList = shortList->next;
longList = longList->next;
}

}
}
//若不相交，则直接返回空
return NULL;
}``````

### 3、复制带随机指针的链表

• 链接直达：

• 题目：

•  思路：

``````struct Node* cur = head;
//1、拷贝节点链接在原节点后面
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;
}``````

``````//2、更新拷贝节点的random
while (cur)
{
struct Node* copy = cur->next;
if (cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = cur->next->next;
}``````

最后，恢复原链表，把拷贝链表链接在一起

``````//3、拷贝节点剪下来，链接到一起
struct Node* copyTail = NULL;
while (cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
cur->next = next;
if (copyTail == NULL)
{
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
cur = next;
}
}
``````
• 总代码如下：
``````struct Node* copyRandomList(struct Node* head) {
//1、拷贝节点链接在原节点后面
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;
}
//2、更新拷贝节点的random
while (cur)
{
struct Node* copy = cur->next;
if (cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
cur = cur->next->next;
}
//3、拷贝节点剪下来，链接到一起
struct Node* copyTail = NULL;
while (cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
cur->next = next;
if (copyTail == NULL)
{
}
else
{
copyTail->next = copy;
copyTail = copyTail->next;
}
cur = next;
}