链表翻转相加，结果再翻转 class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here //链表反转 相加 再反转 ListNode* newList1 = reverse(head1...

灵活运用链表长度加减法，对链表分段相加长度相同 a+b+c = c+b+a 双指针指向相同即使共同部分b的入口节点，a+b到尾部则跳转另一链表c+b，同理，c+b到尾部则跳转a+b。 class Solution { public: ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) { ListNode* first = pHead1; ListNode* second = pHead2; while(first != second){ first = (first==nullptr...

快慢指针思路 快指针抢跑n个节点 class Solution { public: /** * * @param head ListNode类 * @param n int整型 * @return ListNode类 */ ListNode* removeNthFromEnd(ListNode* head, int n) { // write code here ListNode* newList = new ListNode(-1); newList->next = ...

快慢指针思路 由于最后的几个节点，可以让快指针先抢跑k个节点，再以相同的速度向后迭代，当快指针先到nullptr则慢指针节点为最后几个系欸但的头节点 fast->next 抢跑k个节点 class Solution { public: /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param pHead ListNode类 * @param k int整型 * @return ListNode类 */ ListNode* FindKthToT...

快慢指针解题 在指针向后迭代的过程中，快指针比慢指针快一倍，把链表长度顺序切割为： 头节点到入口节点：a 入口节点到相遇节点：b 相遇节点到入口节点：c 可得以下公式 2(a+b) = a+b+c+b => a = c 思路是：相遇后快指针指向头节点，并且速度平齐慢指针 class Solution { public: ListNode* EntryNodeOfLoop(ListNode* pHead) { //成环前提 至少两个以上节点 if(pHead==nullptr||pHead->next==nullptr){ ...

有环问题第一思考快慢双指针 快指针每次前进2，慢指针每次前进1，当两者相遇fast==slow则成环，当快指针指向nullptr则为false出口 fast->next->next slow->next 需要额外注意的是，链表成环必须要满足2个及以上节点数量 class Solution { public: bool hasCycle(ListNode *head) { //判断环，直接思考快慢指针 if(head==nullptr||head->next==nullptr){ return false;...

采用归并排序的思路 后续更新

链表迭代思路 面对两个有序链表，初始化一个新节点（-1） A->B.... C->D.... 我们要做的是比较A和C的大小，-1指向更小的节点，更小的节点向后迭代,随后temp = temp->next迭代 temp-> a<=c?a:c a = b temp=temp->next 最后的退出机制是当有一个链表为空时，此时temp指向不为空的链表节点 temp-> a == nullptr?a:c 最后返回(-1)->next,将-1内存删除，避免内存泄漏 class Solution { public: ListNode* Me...

链表相关的算法思路，由于没有索引，通常采用递归、迭代两种方式，在翻转上的思考来讲，还是以迭代结合分段的思路更为清晰，并且内存消耗更小 class Solution { public: ListNode* reverseKGroup(ListNode* head, int k) { // write code here ListNode* tail = head; for(int i=0;i<k;i++){ //链表长度不足k，直接return if(tail == nullptr){ ...

/** * struct ListNode { * int val; * struct ListNode *next; * }; */ class Solution { public: /** * * @param head ListNode类 * @param m int整型 * @param n int整型 * @return ListNode类 */ ListNode* reverseBetween(ListNode* head, int m, int n) { ListNod...

递归的思路 递归出口 翻转最后要将末尾节点视作头节点，一直递归到head->next == nullptr,保存末尾节点。同时如果链表为空直接return。 递归回溯 从末尾-1节点开始回溯时，需要将末尾节点的next指向前一节点，即pHead->next->next = pHead 为了避免形成循环链表们需要将pHead->next == nullptr。 时间复杂度计算 时间复杂度o(n) 遍历整个链表 空间复杂度o(n) 递归栈的内存使用 class Solution { public: ListNode* ReverseList(ListNode* pH...

IPSC-应用软件实习生