前言
今日练习目的：掌握如何遍历链表，以及改变节点的next指向。
206：反转链表
题目要求：给定一个单链表的头节点head
要求：反转链表，并返回反转后的链表
核心思路
使用三个指针：
prev：当前节点的前一个节点
cur ：当前正在处理的节点
next：临时保存 cur 的下一个节点
代码实现
classSolution{publicListNodereverseList(ListNodehead){ListNodeprev=null;ListNodecur=head;while(cur!=null){ListNodenext=cur.next;// 保存下一个节点cur.next=prev;// 反转指针prev=cur;// prev 前进cur=next;// cur 前进}returnprev;}}总结
掌握链表的语法:listNode prev=null
203：移除链表元素
题目要求：给定一个链表头节点head和一个值val。
要求：删除链表中所有等于val的节点，并返回head
核心思路
引入虚拟头节点dummy，防止第一个元素就是需要被删除元素
遍历的逻辑：
如果 cur.next.val == val：
删除 cur.next
否则：
cur 向后移动
代码实现
classSolution{publicListNoderemoveElements(ListNodehead,intval){// 虚拟头节点ListNodedummy=newListNode(0);dummy.next=head;ListNodecur=dummy;while(cur.next!=null){if(cur.next.val==val){cur.next=cur.next.next;// 删除节点}else{cur=cur.next;// 移动指针}}returndummy.next;}}总结
掌握虚拟头节点的创建：ListNode dummy=new ListNode(0); dummy.next=head
遍历的逻辑
返回dummy的语法：return dummy.next
21：合并两个有序链表
题目要求：给定两个升序排列的链表list1和list2
要求：将他们合并成一个新的升序链表并返回
核心思路
双指针+虚拟头节点
将两个链表取出元素进行比较并拼接
最后将剩余链表拼接
代码实现
ListNodedummy=newListNoed(0);ListNodecur=dummy;ListNodep1=list1;ListNodep2=list2;while(p1!=null&&p2!=null){if(p1.val<p2.val){cur=p1.val;p1=p1.next;}else{cur=p2.next;p2=p2.next;}cur=cur.next;}//拼接剩余if(p1!=null){cur=p1;}else{cur=p2;}returndummy.next;总结
要求做到升序链表，想到用双指针来判断头节点的大小
用剩余链表直接收尾
2：两数相加
题目要求：给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
核心思路
代码实现
ListNodedummy=newListNode(0);ListNodecur=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;cur.next=newListNode(sum%10);cur=cur.next;}returndummy.next;总结
本题的核心是：链表逐位相加 + 进位 carry
核心三要素
- sum = l1 + l2 + carry
- 当前位 = sum % 10
- carry = sum / 10
