继续练习题:
7.判断链表是不是回文结构
对于一个链表,设计一个时间复杂度O(n)空间复杂度O(1)的算法,判断是否为回文结果
给定一个链表的头指针A,返回一个bool值代表其是否为回文结构.
测试样例:1->2->2->1
返回:ture
bool chkPalindrome(ListNode* A){
//找到中间节点
if (A == NULL || A->next == NULL)
return ture;
ListNode* fast, *slow;
fast = slow = A;
while (fast && fast->next){
slow = slow->next;
fast = fast->next->next;
}
ListNode* prev = NULL;
ListNode* cur = slow;
//逆转
while (cur){
ListNode* next = cur->next;
//头插
cur->next = prev;
prev = cur;
cur = next;
}
//比较
while (A && prev){
if (A->val != prev->val)
return false;
A = A->next;
prev = prev->next;
}
return ture;
}
8.输入两个链表,找出它们第一个相交的节点
struct ListNode* getIntersectionNode(struct List* headA,
struct ListNode* headB){
int lenA = 0;
int lenB = 0;
struct ListNode* curA = headA, *curB = headB;
while (curA){
++lenA;
curA = curA->next;
}
while (curB){
++lenB;
curB = curB->next;
}
int gap = abs(lenA - lenB);
//首先让长链表先走gap步
struct listNode* longList = headA, *shortList = headB;
if (lenB > lenA){
longList = headB;
shortList = headA;
}
while (gap--){
longList = longList->nest;
}
//两个链表同时遍历
while (longList && shortList){
//判断是否同一个节点:比较节点的地址
if (longList == shortList)
return longList;
longList = longList->next;
shortList = shortList->next;
}
return NULL;
}
9.给定一个链表,判断链表中是否有环
要求:如果链表中有某节点,可以通过连续跟踪next指针再次到达,则链表中存在环.为了表示给定链表中的环,我们使用证书pos来表示链表尾链接到链表中的位置(索引从0开始).如果pos是-1,则在该链表中没有环.注意:pos不作为参数进行传递,仅仅是为了标识链表的实际情况.如果链表中存在环,则返回ture,否则返回false.
快慢指针:fast:每次走两步slow:每次走一步
fast:NULL --> 没有环
fast == slow -->有环
bool hasCycle(struct ListNode* head){
struct ListNode* fast, *slow;
fast = slow = head;
while (fast && fast->naxt){
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return ture;
}
return false;
}
10.给定一个链表,返回链表开始入环的第一个节点.如果链表无环,则返回NULL.
思路:假设环的长度C 入口节点到相遇点的距离X 起点到入口点的距离 L
慢指针走过的节点个数:L+X
快指针走过的节点数:L+X+N * C(N > 0)
快指针节点个数 = 2 * 慢指针节点个数
解得(N - 1)C + C - X = L
//获取相遇点
struct ListNode* listCycle(struct ListNode* nead){
struct ListNode* fast, *slow;
fast = slow = head;
while (fast && fast->next){
fast = fast->next->next;
slow = slow->next;
if (fast == slow){
return fast;
}
return NULL;
}
struct ListNode* detectCyle(struct ListNode* head){
struct ListNode* node = listCycle(head);
if (node){
//分别从相遇点和起点开始走,每次走一步
while (node){
if (node == head){
return node;
}
node = node->next;
head = head->next;
}
}
return NULL;
}
}
11.给定一个链表,每个节点包含一个额外增加的随机指针,该指针可以指向链表中任何节点或者空节点.要求返回这个链表的深度拷贝
拷贝数据:新的数据存放元素链表中,存放在当前需要拷贝的数据的next位置
拷贝random指向:拷贝当前指针的下一个地址copy->next = cur->random->next
拆链:
struct node* copyRandomList(struct Node* head){
if (head == NULL);
return head;
//1.拷贝数据
struct Node* cur = head;
while (cur){
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->val = cur->val;
struct Node* next = cur->next;
cur->next = newNode;
newNode->next = next;
cur = next;
}
//2.拷贝random
cur = head;
while (cur){
struct Node* copy = cur->next;
if (cur->random)
copy->random = cur->random->next;
else
copy->random = NULL;
}
//3.拆链
struct Node* newHead = NULL;
cur = head;
while (cur){
struct Node* copy = cur->next;
struct Node* next = copy->next;
if (newHead == NULL)
newHead = copy;
cur->next = next;
if (next)
copy->next = next->next;
else
copy->next = NULL;
cur = copy->next;
}
return newHead;
}
12.对链表进行插入排序
插入排序:在已经排好的序列中,插入新的数据.前提/假设:第一个数据是有序的.插入过程:待插入的数据从有序序列的最后一个位置开始向前遍历,找到一个前一个比他小或者等于的数据,待插入的数据放入次数据的后面.
/*
Definition for singly-linked list.
struct ListNode{
int val;
ListNode* next;
ListNode(int x) : val(x),next(NULL){};
};
*/
class Solution{
public:
ListNode* insertionSortList(ListNode* head){
if (head == NULL || head->next == NULL)
return head;
//假设第一个数据有序
struct ListNode* tail, *cur, *prev, *node;
//tail:有序链表的尾节点
tail = head;
cur = head->next;
while (cur){
//如果待插入数据小于有序数据的最后一个数据需要遍历
if (cur ->val < tail->val){
//从头结点开始遍历
prev = NULL;
node = head;
//从有序数据中找到第一个大于待插入数据的位置
while (node && node->val <= cur->val){
prev = node;
node = node->next;
}
//prev cur node
tail->next = cur->next;
cur->next = node;
if (prev)
prev->next = cur;
else
head = cur;
//排序下一个数据
cur = tail->next;
}
else{
tail = tail->next;
cur = tail->next;
}
}
return head;
}
};
链表相关的题还可以多刷等有整体吸收了再刷题.
