【学习记录】第六周

一、本周核心学习内容

1. 链表基础知识复习
   单链表结构回顾：复习了链表节点的基本定义、链表的创建、插入、删除和遍历操作
   链表与数组对比：重新梳理了链表在动态内存分配、插入删除效率等方面的优势
   常见链表操作：包括反转链表、合并有序链表、检测环等基础算法
2. 双指针技术深入掌握
   本周重点学习了三种双指针应用场景：

快慢指针应用

// 1. 检测链表环structListNode{intval;structListNode*next;};inthasCycle(structListNode*head){if(head==NULL||head->next==NULL){return0;}structListNode*slow=head;structListNode*fast=head;while(fast!=NULL&&fast->next!=NULL){slow=slow->next;// 慢指针走一步fast=fast->next->next;// 快指针走两步if(slow==fast){// 两指针相遇，说明有环return1;}}return0;// 无环}

左右指针应用

// 2. 反转链表（双指针实现）structListNode*reverseList(structListNode*head){structListNode*prev=NULL;structListNode*curr=head;while(curr!=NULL){structListNode*nextTemp=curr->next;// 暂存下一个节点curr->next=prev;// 反转指针方向prev=curr;// 前指针后移curr=nextTemp;// 当前指针后移}returnprev;// 新的头节点}

前后指针应用`

// 3. 删除链表倒数第N个节点structListNode*removeNthFromEnd(structListNode*head,intn){structListNodedummy={0,head};// 虚拟头节点简化边界处理structListNode*first=&dummy;structListNode*second=&dummy;// 让first指针先走n+1步for(inti=0;i<=n;i++){first=first->next;}// 两个指针同步移动，直到first到达末尾while(first!=NULL){first=first->next;second=second->next;}// 删除目标节点structListNode*toDelete=second->next;second->next=second->next->next;returndummy.next;}

快慢指针找链表中点

// 找到链表的中间节点structListNode*findMiddle(structListNode*head){if(head==NULL||head->next==NULL){returnhead;}structListNode*slow=head;structListNode*fast=head;// 快指针每次走两步，慢指针每次走一步while(fast!=NULL&&fast->next!=NULL){slow=slow->next;fast=fast->next->next;}returnslow;// 当快指针到达末尾时，慢指针刚好在中间}

双指针判断回文链表

// 判断链表是否为回文结构intisPalindrome(structListNode*head){if(head==NULL||head->next==NULL){return1;}// 步骤1：找到中点structListNode*slow=head;structListNode*fast=head;while(fast->next!=NULL&&fast->next->next!=NULL){slow=slow->next;fast=fast->next->next;}// 步骤2：反转后半部分链表structListNode*secondHalf=reverseList(slow->next);// 步骤3：比较前后两部分structListNode*p1=head;structListNode*p2=secondHalf;intresult=1;while(result&&p2!=NULL){if(p1->val!=p2->val){result=0;}p1=p1->next;p2=p2->next;}// 步骤4：恢复原链表（可选）slow->next=reverseList(secondHalf);returnresult;}

双指针解决两数相加

// 两个链表表示的非负整数相加structListNode*addTwoNumbers(structListNode*l1,structListNode*l2){structListNodedummy={0,NULL};structListNode*curr=&dummy;intcarry=0;// 进位while(l1!=NULL||l2!=NULL||carry!=0){intsum=carry;if(l1!=NULL){sum+=l1->val;l1=l1->next;}if(l2!=NULL){sum+=l2->val;l2=l2->next;}carry=sum/10;// 计算进位curr->next=(structListNode*)malloc(sizeof(structListNode));curr->next->val=sum%10;// 当前位结果curr->next->next=NULL;curr=curr->next;}returndummy.next;}