首页 > 代码库 > 链表题目总结(第二篇)
链表题目总结(第二篇)
第一篇里面的问题都是操作一个链表的情况，这一篇主要说说多个链表的一些问题
（１）合并两个已经排序好的链表
／／l1, l2两个指针不断的后移 ListNode *MergeSortedLists(ListNode *l1, ListNode *l2) { ListNode newhead(0), *pos = &newhead; while(l1 || l2){ if(!l1) return (pos->next = l2, newhead.next); if(!l2) return (pos->next = l1, newhead.next); (l1->val < l2->val)? (pos = pos->next = l1, l1 = l1->next) : (pos = pos->next = l2, l2 = l2->next); } return newhead.next; }
（２）判断两个无环链表是否相交
// 判断两个链表是否相交，只需要判断两个链表最后一个节点是否为同一个即可bool isMeetList(ListNode *pHead1, ListNode *pHead2){ if(!pHead1 || !pHead2) return false; ListNode *pos1 = pHead1, *pos2 = pHead2; while(pos1->next){ pos1 = pos1->next; } while(pos2->next){ pos2 = pos2->next; } return pos1 == pos2;}
（３）寻找两个无环链表第一个相交点
// 找到两个链表第一个相交点，首先遍历两个链表，得到两个链表的长度，比如说l1, l2// 然后先移动较长的那个链表（比如l1>l2），移动l1-l2步，这样双方剩余的节点数就相等了// 接着以前往后走，第一次相遇的点就是答案ListNode *getFirstMeet(ListNode *pHead1, ListNode *pHead2){ if(!pHead1 || !pHead2) return NULL; ListNode *pos1 = pHead1, *pos2 = pHead2; int l1 = 0, l2 = 0; while(pos1->next){ l1++; pos1 = pos1->next; } while(pos2->next){ l2++; pos2 = pos2->next; } if(pos1 != pos2) return NULL; pos1 = l1 > l2? pHead1 : pHead2; pos2 = l1 > l2? pHead2 : pHead1; int count = l1 > l2? l1 - l2 : l2 -l1; while(count-- > 0){ pos1 = pos1->next; } while(pos1 && pos2){ if(pos1 == pos2) return pos1; pos1 = pos1->next; pos2 = pos2->next; } }
链表题目总结(第二篇)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。