# 链表面试题

## ❣️1.题目

1 <= Node.val <= 100

## ❣️2.解答：快慢指针法

struct ListNode*middleNode(struct ListNode* head)
{
while(fast &&fast->next)
{
slow =slow->next;
fast =fast->next->next;
}
return slow;
}

# 💝2.21. 合并两个有序链表

21. 合并两个有序链表

## ❣️1.题目

• 两个链表的节点数目范围是 [0, 50]
• -100 <= Node.val <= 100
• l1l2 均按 非递减顺序 排列

## ❣️2.解答 ：双指针遍历两个链表

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

# 💝3.OR36 链表的回文结构

1->2->2->1

## ❣️2.解答：快慢指针和链表反转

reverseList：链表反转函数，输入一个链表头节点，返回反转后的链表头节点。middleNode：快慢指针找中间节点函数，输入链表头节点，返回中间节点。chkPalindrome：判断是否为回文链表的函数，输入链表头节点，返回是否为回文链表。

class PalindromeList {
public:
struct ListNode* reverseList(struct ListNode* head) {
while (cur) {
struct ListNode* next = cur->next;// 头插
cur = next;
}
}
struct ListNode* middleNode(struct ListNode* head) {
while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
return false;
}
return true;
}

};

# 💝4.138.随机链表的复制

138. 随机链表的复制

## ❣️ 1.题目：

• val：一个表示 Node.val 的整数。
• random_index：随机指针指向的节点索引（范围从 0n-1）；如果不指向任何节点，则为  null

• 0 <= n <= 1000
• -104 <= Node.val <= 104
• Node.randomnull 或指向链表中的节点。

## ❣️2.解答

struct Node* copyRandomList(struct Node* head) {
while(cur)
{
struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
copy->val = cur->val;
copy->next = cur->next;
cur->next = copy;
//cur = copy->next;
cur = cur->next->next;
}
while(cur)
{
struct Node* copy = cur->next;
if(cur->random == NULL)
{
copy->random = NULL;
}
else
{
copy->random = cur->random->next;
}
//cur = copy->next;
cur = cur->next->next;
}
struct Node* newhead = NULL,*tail = NULL;
while(cur)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
if(tail == NULL)
{
}
else
{
tail->next = copy;
tail = tail->next;
}
cur->next = next;
cur = next;
}

}

|
1月前
|

LeetCode 83题：删除排序链表中的重复元素【面试】
LeetCode 83题：删除排序链表中的重复元素【面试】
12 0
|
2月前
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
【一刷《剑指Offer》】面试题 17：合并两个排序的链表
26 0
|
2月前
【一刷《剑指Offer》】面试题 16：反转链表
【一刷《剑指Offer》】面试题 16：反转链表
32 0
|
2月前
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
【一刷《剑指Offer》】面试题 15：链表中倒数第 k 个结点
27 0
|
2月前
|

【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点
【一刷《剑指Offer》】面试题 13：在 O(1) 时间删除链表结点
32 0
|
2月前
【一刷《剑指Offer》】面试题 5：从尾到头打印链表
【一刷《剑指Offer》】面试题 5：从尾到头打印链表
23 0
|
2月前
|

31 0
|
2月前
|

31 0
|
2月前
|

19 0
|
2月前
|

27 0