建站系统开发,seo服务器选择,网站备案证图片,龙岩做网站开发哪家厉害160. 相交链表 本质上是走过自己的路#xff0c;再走过对方的路#xff0c;这是求两个链表相交的方法 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//本质上是走过自己的路#xff0c;再走过对方的路if(headA NULL|| headB NULL){return NULL;}Lis…160. 相交链表 本质上是走过自己的路再走过对方的路这是求两个链表相交的方法 ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {//本质上是走过自己的路再走过对方的路if(headA NULL|| headB NULL){return NULL;}ListNode* temp_a headA;ListNode* temp_b headB;while(temp_a!temp_b){if(temp_a NULL){temp_a headB;}else{temp_a temp_a-next;}if(temp_b NULL){temp_b headA;}else{temp_b temp_b-next;}}return temp_a;}双指针法
情况一两个链表相交。这个好判断
情况二两个链表不相交。由于两个链表没有公共节点两个指针也不会同时到达两个链表的尾节点因此两个指针都会遍历完两个链表指针pA 移动了mn 次、指针pB 移动了 nm 次之后两个指针会同时变成空值null此时返回null满足循环条件。
⭕️206. 反转链表
ListNode* reverseList(ListNode* head) {if(head nullptr){return head;}if(head-next nullptr){return head;}ListNode *temp reverseList(head-next);head-next-next head;head-next nullptr;return temp;}上面这段代码是反转列表标准递归代码也很好理解
21. 合并两个有序链表 使用迭代好理解。这道题第一反应就是四种种情况全是空一个是空全不为空。 正常理解就是ifelse if什么的但是这样在写全不为空的时候很麻烦。 下面代码一个while(l1 l2)就解决了上面的问题很巧妙很值得记住。必须全不为空才能进入循环有一个是空指针就不能进入这样代码好写很多很多 ListNode *head new ListNode(-1);ListNode *pre head;while(l1 l2){ListNode* temp1 l1;ListNode* temp2 l2;if(l1-val l2-val){pre-next l2;l2 l2-next;}else{pre-next l1;l1 l1-next;}pre pre-next;}if(l1 nullptr){pre-next l2;}if(l2 nullptr){pre-next l1;}return head-next;}141. 环形链表 思路用快慢指针如果是环形链表会相交 主要点在于while的循环条件一定要针对快指针进行条件判断同时用而不是|| bool hasCycle(ListNode *head) {ListNode* fast head;ListNode* slow head;if(head nullptr || head-next nullptr){return false;}while(fast ! nullptr fast-next ! nullptr){slow slow-next;fast fast-next-next;if(fast slow){return true;}}return false;}142. 环形链表 II 这道题自己画图就知道了本质就是一道数学题。 判断有无环 a(n1)bnc2(ab)⟹ac(n−1)(bc) 即ac 当第一次相遇时快指针回到头结点慢指针不动。两个指针按照相同速度走相遇点即为环的入口点。 ListNode *detectCycle(ListNode *head) {ListNode* slow head; ListNode* fast head; while(fast fast-next){ slow slow-next; fast fast-next-next; if(slow fast){ fast head; while(fast ! slow){ fast fast-next; slow slow-next; } return fast; } } return nullptr;
}19. 删除链表的倒数第 N 个结点 当碰到链表第几个节点的时候双指针的思想可能正合适。 我们可以设想假设设定了双指针 p 和 q 的话当 q 指向末尾的 NULLp 与 q 之间相隔的元素个数为 n 时那么删除掉 p 的下一个指针就完成了要求。 ListNode* removeNthFromEnd(ListNode* head, int n) { //双指针思想以后这种倒数的长度类型的题目都可以用双指针 ListNode* p head; ListNode* q head; while(n0){ p p-next; n--; } if(!p){ return head-next; } while(p-next){ p p-next; q q-next; } q-next q-next-next; return head;
}24. 两两交换链表中的节点 思路交换节点的题就要有temp-next和temp-next-next。 如果 temp 的后面没有节点或者只有一个节点则没有更多的节点需要交换因此结束交换。否则获得 temp 后面的两个节点 node1(temp-next)和 node2(temp-next-next)通过更新节点的指针关系实现两两交换节点。 下面是错误代码
ListNode* swapPairs(ListNode* head) { ListNode* temp new ListNode(-1); temp-next head; while(temp-nexttemp-next-next){ ListNode* l1 temp-next; ListNode* l2 temp-next-next; temp-next l2; l1-next l2-next; l2-next l1; temp l1; } return head;
}输入1,2,3,4
输出1,4,3
错误原因注意这道题head节点指的是首节点这是最重要一点。其次最开始head节点为1在上面代码交换结束后正常来说为2,1,4,3但是head节点此刻还是1如果返回head则2被漏掉
正确代码
ListNode* swapPairs(ListNode* head) { ListNode* temp new ListNode(-1); temp-next head; ListNode* dummy temp; while(temp-nexttemp-next-next){ ListNode* l1 temp-next; ListNode* l2 temp-next-next; temp-next l2; l1-next l2-next; l2-next l1; temp l1; } return dummy-next;
}
