| 刷题PIA 之 链表 | 您所在的位置：网站首页 › c语言iter=0 › 刷题PIA 之 链表 |
|
0. 刷题BGM : A Day at the Beach - j'san./Pandrezz 1. 反转链表描述：题意简单不赘述 输入：单链表的头结点 pHead 输出：反转链表的表头 算法：前插法 + 迭代 class Solution { public: ListNode* ReverseList(ListNode* pHead) { ListNode* pReverseList = NULL; ListNode* pNode = pHead; ListNode* pPre= NULL; while(pNode != NULL){ ListNode* pNext = pNode->next; if(pNext == NULL){ pReverseList = pNode; } pNode->next = pPre; pPre = pNode; pNode = pNext; } return pReverseList; } };分析：1）创建新的链表指针指向头结点（ListNode* pNode = pHead;），返回整个链表元素。 2）本题由于每迭代后，Pnode与Ppre直接无连接，故直接返回Pnode无法获得正确结果。 3）根据分析 2）可改写 while 循环内容，改写代码如下所示。 while(Pnode != NULL) { ListNode *Pnext = Pnode->next; Pnode->next = Ppre; Ppre = Pnode; if(Pnext != NULL) { Pnode = Pnext; }else { return Pnode; } }TRICK：反转以平移思想为准，从 Pnow->next 到 Ppre 到 Pnow 顺序平移 2. 链表内指定区间反转描述：固定区间实现局部链表反转 输入：单链表的头结点 pHead 输出：局部反转链表的表头 算法：前插法 + 迭代 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include #include #include class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { if(!head & !head->next) return head; ListNode* B = head,* A = new ListNode(-1),* C; int k = m - 1; A->next = head; ListNode* RES = A; while (k--) { B = B->next; A = A->next; } ListNode* T = A; k = n - m; while(k--) { C = B->next; B->next = C->next; C->next = T->next; T->next = C; } return RES->next; } }; 3.合并两个排序的链表描述：合并两个子顺序链表成一个合并顺序链表 输入：两个单链表的头结点 pHead 输出：合并链表 算法：迭代 #include class Solution { public: ListNode* Merge(ListNode* pHead1, ListNode* pHead2) { ListNode* RES = new ListNode(-1); ListNode* A = pHead1,*B = pHead2; ListNode* T = RES; while(A && B) { if(A->val < B->val) { T->next = A; A = A->next; } else { T->next = B; B = B->next; } T = T->next; } if(A) { T->next = A; } else { T->next = B; } return RES->next; } }; 4.判断链表是否有环描述：给出一链表，判断是否带环 输入：单链表的头结点 pHead 输出：带环BOOL 算法：双指针 + 快慢指针 class Solution { public: bool hasCycle(ListNode *head) { bool res = false; ListNode* F = head,* S = head; while(F->next && F) { F = F->next->next; S = S->next; if(F == S) { res = true; break; } } return res; } };TRICK ：判断条件以快指针 F 及 F -> next 为条件。 5. 链表中环的入口结点描述：给出一链表，判断是否带环 ,并输出入口节点 输入：两个单链表的头结点 pHead 输出：入口节点，若无环输出NULL 算法：双指针 + 快慢指针 #include class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { ListNode* F = pHead, * S = pHead; int tag = 0; while (F->next && F) { S = S->next; F = F->next->next; if (F == S) { tag = 1; break; } } if (tag == 0) return NULL; else { S = pHead; while (S != F && tag == 1) { S = S->next; F = F->next; } return S; } }TRICK ：判断为有环后，将慢指针重置，两指针根据一次平移一格获得交汇点即为入口点。 6.链表中倒数最后k个结点描述：给出一链表，给出链表后k个结点 输入：单链表的头结点 pHead 输出：后k个结点的头结点 算法：。。。 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* FindKthToTail(ListNode* pHead, int k) { int num = 0; ListNode* A = pHead; while(A) { A = A ->next; num++; } if(num < k) return NULL; else{ for(int i(0);inext; } return pHead; } } 7. 删除链表的倒数第n个节点描述：题意简单不赘述 输入：单链表的头结点 pHead 输出：除倒数第k个的链表表头 算法：。。。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include #include #include class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here int num = 0; ListNode* A = head; ListNode* res = new ListNode(-1); res->next = head; ListNode* temp = res; while(A) { A = A->next; num++; } for(int i(0);inext; } temp->next = temp->next->next; return res->next; } };TRICK：返回值可能包含前置链表时，实用动态创建链表 8. 两个链表的第一个公共结点描述：题意简单不赘述 输入：两个单链表的头结点 pHead 输出：第一个共同的结点 算法：。。。 /* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) { } };*/ #include class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode* A = pHead1; while (A) { ListNode* B = pHead2; while (B) { if (A->val == B->val && A == B) { return A; } else { B = B->next; } } A = A->next; } return NULL; }TRICK：将A、B两链表遍历成环，即A -> next = NULL 时 A -> next = pHead2，B同理。 9.判断一个链表是否为回文结构描述：题意简单不赘述 输入：单链表的头结点 pHead 输出：BOOL是否为回文标志 算法：。。。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 the head * @return bool布尔型 */ bool isPail(ListNode* head) { // write code here int l = 0; bool res = true; ListNode* A = head; while (A) { A=A->next; l++; } l = l/2; ListNode* B = head; while (l--) { B = B ->next; } B = ReverseList(B); ListNode* C = head; while (B) { if (C->val != B->val) { res = false; } C = C->next; B = B->next; } return res; } ListNode* ReverseList(ListNode* pHead) { ListNode* pReverseList = NULL; ListNode* pNode = pHead; ListNode* pPre= NULL; while(pNode != NULL){ ListNode* pNext = pNode->next; if(pNext == NULL){ pReverseList = pNode; } pNode->next = pPre; pPre = pNode; pNode = pNext; } return pReverseList; } }; 10. 删除有序链表中重复的元素-I描述：题意简单不赘述 输入：单链表带重复元素的头结点 pHead 输出：无重复元素的链表头结点 算法：。。。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @return ListNode类 */ ListNode* deleteDuplicates(ListNode* head) { // write code here ListNode* A = new ListNode(-1); A->next = head; ListNode* T = head; while(T&&T->next) { if (T->val == T->next->val) { T->next = T->next->next; }else { T = T->next; } } return A->next; } 11.链表的奇偶重排描述：给一个单链表，使奇数编号项在前输出偶数编号项在后输出 输入：单链表带重复元素的头结点 pHead 输出：奇偶重排元素的链表头结点 算法：。。。 /** * struct ListNode { * int val; * struct ListNode *next; * ListNode(int x) : val(x), next(nullptr) {} * }; */ #include class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param head ListNode类 * @return ListNode类 */ ListNode* oddEvenList(ListNode* head) { // write code here if(!head || !head->next) return head; ListNode* A = head,* B = head->next,* mid = head->next; while (B&&B->next) { A->next = A->next->next; B->next = B->next->next; A = A->next; B = B->next; } A->next = mid; return head; } }; 12 单链表的排序描述：题意简单不赘述 输入：单链表无序的头结点 pHead 输出：有序链表头结点 算法：。。。 /** * struct ListNode { * int val; * struct ListNode *next; * }; */ #include #include #include class Solution { public: /** * * @param head ListNode类 the head node * @return ListNode类 */ ListNode* sortInList(ListNode* head) { // write code here if (!head) { return head; } ListNode* iter = head; vector array; while (iter) { array.push_back(iter->val); iter = iter->next; } sort(array.begin(),array.end()); int i = 0; iter = head; while (iter) { iter->val = array[i++]; iter = iter->next; } delete iter; return head; } };TRICK：将链表内容存入vexctor，再通过sort排序，最后导入链表中。 |
| CopyRight 2018-2019 实验室设备网 版权所有 |