目录
一、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
二、编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前
三、 链表的回文结构
四、 输入两个链表,找出它们的第一个公共结点
五、 给定一个链表,判断链表中是否有环
六、 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL
七、 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝
不要躺平,去发光!
一、 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的
https://leetcode.***/problems/merge-two-sorted-lists/
代码1展示:(不带头)
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
if (list1 == NULL)
{
return list2;
}
if (list2 == NULL)
{
return list1;
}
struct ListNode* head = NULL;
struct ListNode* tail = NULL;
while (list1 && list2)
{
struct ListNode* next1 = list1->next;
struct ListNode* next2 = list2->next;
if ((list1->val) < (list2->val))
{
if (tail == NULL)
{
head = list1;
tail = list1;
}
else
{
tail->next = list1;
tail = list1;
}
list1 = next1;
}
else
{
if (tail == NULL)
{
head = list2;
tail = list2;
}
else
{
tail->next = list2;
tail = list2;
}
list2 = next2;
}
}
if (list1 != NULL)
{
tail->next = list1;
}
if (list2 != NULL)
{
tail->next = list2;
}
return head;
}
思路:每次取小的节点尾插到新的节点
注意:其中一个为空的情况要注意
有头单链表:head->next指的是第一个节点的地址(带头,相当于开头多了一个节点,但是节点里面的val不确定,next指向下一个节点); 无头单链表:head指的是第一个节点的地址; OJ题默认不带头
代码2展示:(带头)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2){
struct ListNode* head = (struct ListNode*)malloc(sizeof(struct ListNode));//创建一个头
struct ListNode* tail = head;
head->next = NULL;//就是含有值的节点的第一个
while (list1 && list2)
{
struct ListNode* next1 = list1->next;
struct ListNode* next2 = list2->next;
if ((list1->val) < (list2->val))
{
tail->next = list1;
tail = list1;
list1 = next1;
}
else
{
tail->next = list2;
tail = list2;
list2 = next2;
}
}
if (list1 != NULL)
{
tail->next = list1;
}
if (list2 != NULL)
{
tail->next = list2;
}
struct ListNode* list = head->next;
free(head);
return list;
}
思路:每次取小的节点尾插到新的节点
注意:mallloc的一个地址,到最后要进行释放。
二、编写代码,以给定值x为基准将链表分割成两部分,所有小于x的结点排在大于或等于x的结点之前
https://www.nowcoder.***/practice/0e27e0b064de4eacac178676ef9c9d70?tpId=8&&tqId=11004&rp=2&ru=/activity/oj&qru=/ta/cracking-the-coding-interview/question-ranking
代码展示:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
class Partition {
public:
ListNode* partition(ListNode* pHead, int x) {
// write code here
struct ListNode* LessHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* LessTail = LessHead;
struct ListNode* GreaterHead = (struct ListNode*)malloc(sizeof(struct ListNode));
struct ListNode* GreaterTail = GreaterHead;
struct ListNode* cur = pHead;
while (cur != NULL)
{
if (cur->val < x)
{
LessTail->next = cur;
LessTail = cur;
}
else
{
GreaterTail->next = cur;
GreaterTail = cur;
}
cur = cur->next;
}
GreaterTail->next = NULL;
LessTail->next = GreaterHead->next;
struct ListNode* list = LessHead->next;
free(LessHead);
free(GreaterHead);
return list;
}
};
思路:小于x的插入到一个链表,大于等于x的插入到一个链表,链表1和链表2合并(用带头的)
注意:链表2的最后一项要指向NULL,如果不指向NULL,就可能造成死循环【链表的题,要注意头和尾】
三、 链表的回文结构
https://www.nowcoder.***/practice/d281619e4b3e4a60a2***66ea32855bfa?tpId=49&&tqId=29370&rp=1&ru=/activity/oj&qru=/ta/2016test/question-ranking
代码展示:
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};*/
struct ListNode* reverseList(struct ListNode* head){
struct ListNode* cur = head;
struct ListNode* prev = NULL;
while(cur)
{
struct ListNode* next = cur->next;
cur ->next = prev;
prev = cur;
cur = next;
}
return prev;
}
struct ListNode* middleNode(struct ListNode* head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && (fast ->next))
{
slow = slow ->next;
fast = fast->next->next;
}
return slow;
}
class PalindromeList {
public:
bool chkPalindrome(ListNode* A) {
// write code here
struct ListNode* mid = middleNode(A);
struct ListNode* rHead = reverseList(mid);
while (A && rHead)
{
if (A->val == rHead->val)
{
A = A->next;
rHead = rHead->next;
}
else
{
return false;
}
}
return true;
}
};
思路:首先找到链表的中间的地址(奇数个)或者是中间的第二个地址(偶数个)作为第二个链表的头,然后逆置第二个链表,然后第原始链表和第二个链表进行比较。(当原始链表和第二个链表有一个是空的时候,就可以跳出循环,说明是回文链表
四、 输入两个链表,找出它们的第一个公共结点
https://leetcode.***/problems/intersection-of-two-linked-lists/description/
代码展示:(思路2)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB)
{
//判断是否相交
struct ListNode* tailA = headA;
struct ListNode* tailB = headB;
int lenA = 1;
int lenB = 1;
while (tailA->next != NULL)
{
tailA = tailA->next;
lenA++;
}
while (tailB->next != NULL)
{
tailB = tailB->next;
lenB++;
}
if (tailA != tailB)
{
return NULL;
}
//找到节点
int gap = abs(lenA - lenB);
//想法值得学习,大小
struct ListNode* shortList = headA;
struct ListNode* longList = headB;
if (lenA > lenB)
{
shortList = headB;
longList = headA;
}
while(gap--)
{
longList = longList->next;
}
while (longList && shortList)
{
if (longList == shortList)
{
return longList;
}
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
思路1:A链表每一个节点和B链表依次比较,如果有相等,就是相交,第一个相等的就是交点。
(判断是否是相交,交点是多少)时间复杂度:O(M*N)
思路2:当尾节点的地址相同的时候,就是相交。(判断是否是相交)
求出两个链表的长度,然后链表长的先走两个链表的差值,然后两个链表一起走,当地址相同的时候,位置就是节点(交点是多少)时间复杂度:O(M+N)
注意:(1)地址相同,不是值相等(值相等不一定是节点)
(2)编译器执行的是语法错误,编译器不能检查出执行逻辑,所以在最后要加上return NULL(因为上面有一个if之后返回一个值,编译器会认为不满足这个if条件的时候没有返回值);
五、 给定一个链表,判断链表中是否有环
https://leetcode.***/problems/linked-list-cycle/submissions/
代码展示:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
bool hasCycle(struct ListNode *head)
{
struct ListNode* slow = head;
struct ListNode* fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
return true;
}
}
return false;
}
思路:[快慢指针]slow一次走一步,fast一次走两步,当slow进环之后,开启追赶模式,最后fast追上slow;不带环fast->next或者fast就会是NULL,带环的话就不会是NULL;
注意:刚开始fast等于slow,所以再循环里面先赋值,后比较
(1)slow一次走一步,fast一次走两步,一定能追上。
当slow走一半的时候,fast开始进环。此时两者的距离为N,每次之后,距离会减少1,所以就一定能追上。【距离为0,追上】
(2)slow一次走一步,fast一次走三步,不一定能追上。
当slow走1/3的时候,fast开始进环。此时两者的距离为N,每次之后,距离会减少2,如果距离为奇数,就会错过,【偶数可以追上】,此时距离又为环数-1【偶数追上,奇数就永远追不上】,所以不一定能追上。
六、 给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回 NULL
https://leetcode.***/problems/linked-list-cycle-ii/description/
代码展示:(思路一)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode *detectCycle(struct ListNode *head)
{
struct ListNode* fast = head;
struct ListNode* slow = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
{
struct ListNode* meet = slow;
while (head != meet)
{
meet = meet->next;
head = head->next;
}
return meet;
}
}
return NULL;
}
思路1:假设,进入环之前的距离为L;slow两者相遇后之前,进入环之后走的距离x;进入环之后两者的距离为N ;环的长度为C [快慢指针]slow一次走一步,fast一次走两步,fast是slow的两倍【slow绝对不会走一圈被fast追上,而是没有走一圈就被fast给追上了,因为当slow进入环之后,两者的距离为N,N肯定小于环数,所以两者相遇的时候,slow肯定没有走完一圈,所以slow走得距离为进入环之前的距离L+两者相遇后之前,进入环之后走的距离x即L+x;fast走的距离为nC+L+x; n*C+L+x=2(L+x),----n*C=L+x;n为未知数】【slow进环之后,fast不可能走完一圈】n*C=L+x:能证明,一个从进入链表走,一个从相遇的那个节点走,slow和fast在环入口处相遇。
思路2:转换成求链表交点。【从相遇处开始断开】meet作为尾,meet->next作为头 ,head给出,求交点。
七、 给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中的任何节点或空节点。 要求返回这个链表的深度拷贝
https://leetcode.***/problems/copy-list-with-random-pointer/description/
代码展示:
/**
* Definition for a Node.
* struct Node {
* int val;
* struct Node *next;
* struct Node *random;
* };
*/
struct Node* copyRandomList(struct Node* head)
{
struct Node* cur = head;
//拷贝节点链接
while (cur!= NULL)
{
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 != NULL)
{
if (cur->random == NULL)
{
cur->next->random = NULL;
}
else
{
cur->next->random = cur->random->next;
}
cur = cur->next->next;
}
//摘下来、链接
struct Node* copyHead = NULL;
struct Node* copyTail = NULL;
cur = head;
while (cur != NULL)
{
struct Node* copy = cur->next;
struct Node* next = copy->next;
if (copyHead == NULL)
{
copyHead = copyTail = copy;
}
else
{
copyTail->next = copy;
copyTail = copy;
}
cur = next;
}
return copyHead;
}
思路:拷贝每一个节点连接在原节点之后,链接拷贝节点的random,新的random在前面的random的next。最后,把拷贝节点解下来,链接起来。【索引从0开始】
链表其他题
力扣:https://leetcode.***/tag/linked-list/problemset/
牛客网:https://www.nowcoder.***/exam/oj