二、相关练习题
1.中间链表
题目链接:LINK
详细解答:LINK
struct ListNode* middleNode(struct ListNode* head) { //思路1:暴力求解法 /*int length = 0; struct ListNode* pcur = head; while(pcur) { length++; pcur = pcur->next; } length/=2; pcur = head; while(length--) { pcur = pcur->next; } return pcur; */ //思路2:双指针法 struct ListNode* slow = head; struct ListNode* fast = head; while(fast && fast->next) { slow = slow->next; fast = fast->next->next; } return slow; }
2.删除链表中等于给定值 val 的所有结点
题目链接:LINK
多种解题思路:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ //处理*head == val 的情况,使*head!=val while (head && head->val == val) { head = head->next; } //如果是空链表,返回 if(head == NULL) { return NULL; } //走到这里,head不是val并且该链表不为空 struct ListNode* cur = head->next;//如果head为空链表这样写不合法 struct ListNode* pre = head; while (cur != NULL) { if (cur->val == val) { //跳跃 pre->next = cur->next; //free struct ListNode* temp = cur; } else { //下一个跟进cur pre = cur; } //cur不断向前走 cur = cur->next; } return head; }
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* removeElements(struct ListNode* head, int val){ //定义新链表的头尾指针 struct ListNode* newHead = NULL; struct ListNode* newTail = NULL; // struct ListNode* pcur = head; while(pcur) { //不是val,尾插到新链表 if(pcur->val!=val) { if(newHead == NULL) { //链表为空 newHead = newTail = pcur; } else//链表不为空 { newTail->next = pcur; newTail = newTail->next;//更新尾节点 } } //更新pcur指针 pcur = pcur->next; } //加上null if(newTail) { newTail->next = NULL; } //返回 return newHead; }
3.反转链表
题目链接:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { //防止给我一个空的链表,如果说给我一个空链表,那么我们下面的n2->next会报错 if(head == NULL) return head; //指针初始化 struct ListNode* n1 = NULL; struct ListNode* n2 = head; struct ListNode* n3 = n2->next; while(n2) { n2->next = n1;//改变指向 n1 = n2; n2 = n3; if(n3)//如果n3不为空,那么让n3往下走一个 n3 = n3->next; } return n1; }
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* reverseList(struct ListNode* head) { //头插的思路 struct ListNode* newhead = NULL; struct ListNode* pcur = head; while(pcur) { struct ListNode* next = pcur->next; pcur->next = newhead; newhead = pcur; pcur = next; } return newhead; }
4.分割链表
题目链接:LINK
#include<stdio.h> #include<stdlib.h> /* 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* sentry1 = (struct ListNode*)malloc(sizeof(struct ListNode)); struct ListNode* sentry2 = (struct ListNode*)malloc(sizeof(struct ListNode)); //定义指针 struct ListNode* newhead1,*newhead2,*newtail1,*newtail2; newhead1 = newtail1 = sentry1; newhead2 = newtail2 = sentry2; //按照条件分割 struct ListNode* pcur = pHead; while(pcur) { if(pcur->val<x) { newtail1->next = pcur; newtail1 = newtail1->next; } else { newtail2->next = pcur; newtail2 = newtail2->next; } pcur = pcur->next; } //链接list1与list2 newtail1->next = newhead2->next; newtail2->next = NULL; pHead = newhead1->next; free(newhead1); free(newhead2); return pHead; } };
5.链表中倒数第K个结点
题目链接:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k){ struct ListNode* pcur = head; int count = 0; while(pcur) { count++; pcur = pcur->next; } count = count - k; pcur = head; while(count--) { pcur = pcur->next; } return pcur->val; }
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ int kthToLast(struct ListNode* head, int k){ struct ListNode* slow = head; struct ListNode* fast = head; while(k--) { fast = fast->next; } while(fast) { slow = slow->next; fast = fast->next; } return slow->val; }
6.合并链表
题目链接:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) { //考虑空链表的情况: //1.两个链表都是空的 if(list1 == NULL && list2 == NULL) { return NULL; } //2.只有list1是空的 if(list1 == NULL) { return list2; } //3.只有list2是空的 if(list2 == NULL) { return list1; } //走到这里,就说明两个链表都不为空了。 struct ListNode* head = NULL; struct ListNode* tail = NULL; //定义两个指针分别遍历两个链表 struct ListNode* pcur1 = list1; struct ListNode* pcur2 = list2; while(pcur1 && pcur2) { if(pcur1->val < pcur2->val) { if(head == NULL) { head = tail = pcur1; } else { tail->next = pcur1; tail = pcur1; } pcur1 = pcur1->next; } else { if(head == NULL) { head = tail = pcur2; } else { tail->next = pcur2; tail = pcur2; } pcur2 = pcur2->next; } } //走到这里,会出现两种情况,要不剩下list1,要不剩下list2 while(pcur1) { tail->next = pcur1; tail = pcur1; pcur1 = pcur1->next; } while(pcur2) { tail->next = pcur2; tail = pcur2; pcur2 = pcur2->next; } return head; }
7.链表的回文结构
题目链接:LINK
详细解答:LINK
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ //找到中间结点 struct ListNode* middleNode(struct ListNode* head) { //思路2:快慢指针法 struct ListNode* fast = head; struct ListNode* slow = head; while(fast && fast->next)//快指针走到头 { slow = slow->next; fast = fast->next->next; } return slow; } struct ListNode* reverseList(struct ListNode* head) { //逆置链表为空 if(head == nullptr) return head; //不为空 struct ListNode* n1 = nullptr; struct ListNode* n2 = head; struct ListNode* n3 = head->next; while(n2) { //逆置 n2->next = n1; //移动n1、n2、n3指向下一个 n1 = n2; n2 = n3; if(n3)//n3不为空 { n3 = n3->next; } } return n1; } class PalindromeList { public: bool chkPalindrome(ListNode* A) { // write code here //找到中间节点 struct ListNode* pMidNode = middleNode(A); //逆置中间节点及其以后的节点 struct ListNode* pNewMidNode = reverseList(pMidNode); //对比 while(A&&pNewMidNode) { if(pNewMidNode->val!=A->val) { return false; } //向后走 A = A->next; pNewMidNode = pNewMidNode->next; } return true; } };
8.查找相交结点
题目链接:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ #include<math.h> struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //判断是不是相交链表 struct ListNode* pTailA = headA; struct ListNode* pTailB = headB; int skipA = 0;//统计A链表中结点的个数 int skipB = 0;//统计B链表中结点的个数 //统计结点个数 while(pTailA->next) { pTailA=pTailA->next; skipA++; } skipA++;//统计少了一个,给他加上 while(pTailB->next) { pTailB=pTailB->next; skipB++; } skipB++; //不是交点 if(pTailA!=pTailB) { return NULL; } //如果是,那么证明他们一定是相交的了,所以我们要查找出他的交点 int sub = abs(skipA-skipB); struct ListNode* pmin = NULL; struct ListNode* pmax = NULL; if(skipA<skipB) { pmin = headA; pmax = headB; } else { pmin = headB; pmax = headA; } //让长的先走一些,让长短对齐 while(sub--) { pmax = pmax->next; } //找交点 while(pmin!=pmax) { pmin = pmin->next; pmax = pmax->next; } return pmax; }
9.判断有环链表
题目链接:LINK
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ bool hasCycle(struct ListNode *head) { struct ListNode* fast = head; struct ListNode* slow = head; while(fast&&fast->next) { slow=slow->next; fast = fast->next->next; if(fast == slow) { return true; } } return false; }
10.有环链表找入环结点
题目链接:LINK
/** * 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) { slow=slow->next; fast = fast->next->next; if(fast == slow) { struct ListNode * meet = slow; struct ListNode * headx = head; while(meet!=headx) { meet = meet->next; headx = headx->next; } return meet; } } return NULL; }
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) { //首先统计每个链表结点的个数 int count1 = 0; int count2 = 0; struct ListNode *pcur1 = headA,*pcur2 = headB; while(pcur1) { count1++; pcur1 = pcur1->next; } while(pcur2) { count2++; pcur2 = pcur2->next; } struct ListNode *maxhead = headA; struct ListNode *minhead = headB; if(count1 < count2) { maxhead = headB; minhead = headA; } int sub = count1-count2; if(sub<0) { sub = 0-sub; } while(sub--) { maxhead = maxhead->next; } while(minhead!=maxhead) { minhead = minhead->next; maxhead = maxhead->next; } return maxhead; } struct ListNode *detectCycle(struct ListNode *head) { //方法二:转换题目:相交链表 struct ListNode* slow = head,*fast = head; while(fast&&fast->next) { slow = slow->next; fast = fast->next->next; if(slow == fast) { struct ListNode* head1 = slow->next; struct ListNode* head2 = head; slow->next = NULL; struct ListNode* meet = getIntersectionNode(head1,head2); return meet; } } return NULL; }
11.随机链表的复制
题目链接:LINK
/** * Definition for a Node. * struct Node { * int val; * struct Node *next; * struct Node *random; * }; */ struct Node* copyRandomList(struct Node* head) { if(head==NULL) { return NULL; } struct Node* pcur = head; //插入一些复制结点 while(pcur) { struct Node* pushback = (struct Node*)malloc(sizeof(struct Node)); pushback->val = pcur->val; pushback->next = pcur->next; pcur->next = pushback; pcur = pcur->next->next;//调整pcur } //控制拷贝结点的random pcur = head; while(pcur) { //如果原链表的random指向空,那我们新链表也要指向空 if(pcur->random == NULL) { pcur->next->random = NULL; pcur = pcur->next->next; continue; } pcur->next->random = pcur->random->next; pcur = pcur->next->next; } //把拷贝结点放下来 pcur = head; struct Node* pcurx = head->next; struct Node* returnpcurx = pcurx; while(pcur) { pcur->next = pcur->next->next; pcur = pcur->next; //最后一个节点 if(pcurx->next == NULL) { pcurx->next = NULL; break; } pcurx->next = pcurx->next->next; pcurx = pcurx->next; } //返回 return returnpcurx; }
EOF