链表练习题-1
https://developer.aliyun.com/article/1498105
相交链表
方法1:暴力法
A中的每个节点的地址在B链表都找一遍,然后比较,时间复杂度是O(n^2)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { struct ListNode* taila = headA; while(taila) { struct ListNode* tailb = headB; while(tailb) { if(taila == tailb) { return tailb; } tailb = tailb->next; } taila = taila->next; } return NULL; }
方法2
两个链表遍历一遍，然后找出尾节点进行比较地址，相同则继续计算长度，长度大的先走，走到剩下的长度和另外一个链表的长度一样，然后一起走，然后一一比较节点的地址
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(!(headA && headB)) return NULL; struct ListNode* tail1 = headA; struct ListNode* tail2 = headB; 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; struct ListNode* maxh = (conut1 >= conut2 ? headA : headB); struct ListNode* minh = (conut1 >= conut2 ? headB : headA); 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; }
环形链表
这里考察带环链表
代环链表:尾节点的next指向链表的任意节点
看到这里可能会想到遍历一遍,找出尾节点,这样很容易陷入死循环,或者有人想到找节点比较,怎么找,因为节点是不确定的,无法这样
这个题可以使用漏洞法
bool hasCycle(struct ListNode *head) { struct ListNode*tail = head; int a = 10002; while(tail) { if(a==0) return true; a--; tail = tail->next; } return false; }
可以判断如果循环次数超出节点数就可以判断是有环的,否则就是无环的这种方法不推荐
方法2:快慢指针速度差法
slow一次走一步，fast一次走两步,当slow刚刚进入到环里面时
fast和slow的距离就是X,转换成fast追逐slow
v1 t - v2t = X, t = x/(v1 - v2)
bool hasCycle(struct ListNode *head) { struct ListNode* slow = head, *fast = head; 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为环的长度
写成 2(L+x) = n*c + L +x
化简成L = (n-1)*c + c - x
所以我们求出入环点可以这样,一个指针在fast和slow相遇的节点开始循环,一个指针从头节点开始走,最终一定会在入环点相遇
struct ListNode *detectCycle(struct ListNode *head) { if(head == NULL) return NULL; struct ListNode*tail = head; struct ListNode*prev = head; //找出相遇点 while (prev && prev->next) { tail = tail->next; prev = prev->next ->next; //找出相遇点 if(tail == prev) { //开始两个指针走 tail = head; while(tail != prev) { tail = tail->next; prev = prev->next; } return tail; } } return NULL; }
转换相交链表解决
先找出相遇点,然后一个指针指向相遇点的下一个节点,把相遇点的next =NULL,然后一个指针从head开始走,变成找两链表找交点
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { if(!(headA && headB)) return NULL; struct ListNode* tail1 = headA; struct ListNode* tail2 = headB; 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; struct ListNode* maxh = (conut1 >= conut2 ? headA : headB); struct ListNode* minh = (conut1 >= conut2 ? headB : headA); 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; } struct ListNode *detectCycle(struct ListNode *head) { if(head == NULL) return NULL; struct ListNode*tail = head; struct ListNode*prev = head; //找出相遇点 while (prev && prev->next) { tail = tail->next; prev = prev->next ->next; //找出相遇点 if(tail == prev) { //开始两个指针走 tail = head; struct ListNode*p = prev->next; prev->next = NULL; p = getIntersectionNode(tail, p); if(p) return p; } } return NULL; }
合并两个有序链表
思路:这里的思路和顺序表的(两顺序表合成一个顺序表)很像,创建两个指针分别指向l1和l2的头节点,创建一个空链表和一个指针,l1和l2的链表的节点进行判断,然后放入到空链表中,然后把剩下的节点一并插入到链表中
这里的空链表可以是带哨兵位的也可以不要
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: bool chkPalindrome(ListNode* head) { if(head == NULL) return true; //双指针速度差法 struct ListNode *slow = head, *fast = head; 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; slow = head; while(slow && fast) { if(slow->val != fast->val) { return false; } slow = slow->next; fast = fast->next; } return true; //双指针比较 } };
随机链表的复制
思路:
我们可以像上图一样,往每个原节点的后面插入一个和该节点相同值的节点,然后我们在原节点的找到random, 每个原节点的后一个节点就是复制的节点,我们可以通过这种特性把复制的节点的random进行连接,然后创建一个空链表,把复制的节点进行连接,
struct Node* copyRandomList(struct Node* head) { if(head == NULL) return NULL; struct Node *cur = head; 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 cur = head; 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; //开始尾插 cur = head; 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; }
