当前位置：首页 > news >正文

20天速通LeetCodeday09：关于链表

news 2026/4/24 23:17:53

前言

今日练习目的：掌握如何遍历链表，以及改变节点的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;