力扣hot100-链表
概要
链表
(Linked List)是数据结构中的一种,用于存储具有线性关系的数据。在链表中,每个元素称为一个节点(Node),每个节点包含两个部分:一个是数据域
(存储数据),另一个是指针域
(指向下一个节点)。链表的结构使得它在某些情况下比数组更加高效,特别是在插入
和删除
操作上。
链表的类型
-
单向链表(Singly Linked List):
- 每个节点只有一个指向下一个节点的指针。
- 头节点(Head)是链表的起点,尾节点(Tail)指向 null。
-
双向链表(Doubly Linked List):
- 每个节点有两个指针,分别指向前一个节点和下一个节点。
- 头节点的前指针和尾节点的后指针都指向 null。
-
循环链表(Circular Linked List):
- 单向链表或双向链表的变种。
- 尾节点的下一个指针指向头节点,形成一个循环。
题目:相交链表
原题链接:相交链表
题解
核心:其实就是让2个指针走一样的距离,消除步行差,那就一定可以一起走到相交点
因为两个链表如果相交,则它们从相交点到结尾的所有节点都是相同的。因此,我们让指针 p1 和 p2 分别遍历两个链表。如果 p1 到达链表 A 的末尾,则将其重定位到链表 B 的头部;同样地,如果 p2 到达链表 B 的末尾,则将其重定位到链表 A 的头部。这样,两指针最终会在相交点处相遇,即第一个共同节点,即为相交点。
public static ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while (p1 != p2) {
p1 = p1 == null ? headB : p1.next;
p2 = p2 == null ? headA : p2.next;
}
return p1;
}
评论区看到一个【还有句话:走到尽头见不到你,于是走过你来时的路,等到相遇时才发现,你也走过我来时的路。】
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode she = headA;
ListNode he = headB;
// 直到两人相遇
while (she != he) {
if (she != null) {
she = she.next;// 如果她没走到尽头就一直走下去
} else {
she = headB;// 直到尽头也没遇见他,所以她去往他走过的路
}
if (he != null) {
he = he.next;
} else {
he = headA;
}
}
return he;// 返回两人第一次相遇的地方
}
题目:反转链表
原题链接:反转链表
题解
方法1:创建新节点并插入新链表头部,更新新链表头指针
public static ListNode reverseList(ListNode head) {
// 如果链表为空,直接返回null
if (head == null) {
return null;
}
// 初始化新链表的头节点
ListNode root = null;
// 遍历原链表,将节点逐个插入到新链表的头部
while (head != null) {
// 保存当前节点的值
ListNode temp = new ListNode(head.val);
// 将新节点插入到新链表的头部
temp.next = root;
// 更新新链表的头节点
root = temp;
// 移动到下一个节点
head = head.next;
}
// 返回新链表的头节点
return root;
}
下面这个是用next记录了下一节点
public static ListNode reverseList(ListNode head) {
ListNode prev = null; // 用于指向当前节点的前一个节点
while (head != null) {
ListNode next = head.next; // 保存当前节点的下一个节点
head.next = prev; // 反转当前节点的指针
prev = head; // 将 prev 移动到当前节点
head = next; // 将 head 移动到下一个节点
}
return prev; // prev 最后指向的新头节点
}
注意:root = temp;
表示 root 指向 temp 所指向的节点
-
head 的定义:
head 是一个指向链表头节点的
指针
。它用于表示整个链表的起点。
例如,在一个链表 1 -> 2 -> 3 -> null 中,head 指向节点 1。 -
ListNode p = head; 的作用:
这行代码创建了一个新的指针p,并使它指向与 head 相同的节点(即链表的头节点)。
题目:回文链表
原题链接:回文链表
方法1
方法1:把链表的值用数组记录下来
public static boolean isPalindrome(ListNode head) {
ArrayList<Integer> list = new ArrayList<>();
while (head != null) {
list.add(head.val);
head = head.next;
}
for (int i = 0; i < list.size() / 2; i++) {
if (list.get(i) != list.get(list.size() - i - 1)) {
return false;
}
}
return true;
}
方法2
方法2:快慢指针找链表中点+翻转
public boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
// 使用快慢指针找到链表的中间节点
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
// 反转后半部分链表
ListNode secondHalfStart = reverseList(slow);
ListNode firstHalfStart = head;
// 比较前半部分和反转后的后半部分
while (secondHalfStart != null) {
if (firstHalfStart.val != secondHalfStart.val) {
return false;
}
firstHalfStart = firstHalfStart.next;
secondHalfStart = secondHalfStart.next;
}
return true;
}
private ListNode reverseList(ListNode head) {
ListNode prev = null;
while (head != null) {
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
题目:环形链表
原题链接:环形链表
题解
public static boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) {
return true;
}
head = head.next;
}
return false;
}
因为 set
中存储的是链表节点的引用(即 ListNode 对象的引用)。因为 HashSet 使用的是对象的引用进行比较,所以如果两个节点是同一个节点(即内存地址相同),HashSet 会检测到这个重复的引用,从而判断链表中存在环。
题目:环形链表Ⅱ
原题链接:环形链表Ⅱ
题解
public ListNode detectCycle(ListNode head) {
ListNode res = new ListNode();
HashSet<ListNode> set = new HashSet<>();
while (head != null) {
if (!set.add(head)) {
return head; //返回节点即可
}
head = head.next;
}
return null;
}
其实理解了环形链表
这个题就很简单。在环形链表
中,只需改动:返回true的时候返回节点即可,返回false的时候返回null
题目:合并两个有序链表
原题链接:合并两个有序链表
题解
- 初始化:创建一个
哑节点
res
作为合并后链表的头节点,temp
用于构建新链表。【哑节点简化了边缘情况处理,不需要特别处理头节点】 - 遍历和比较:同时遍历
list1
和list2
,将较小节点链接到temp
后,并移动list1
或list2
的指针。 - 处理剩余节点:在遍历结束后,将剩余的非空链表直接链接到
temp
后。 - 返回结果:返回
res.next
,跳过哑节点,得到合并后的链表。
public static ListNode mergeTwoLists(ListNode list1, ListNode list2) {
ListNode res = new ListNode(0);
ListNode temp = res;
while (list1 != null && list2 != null) {
if (list1.val < list2.val) {
temp.next = list1;
list1 = list1.next;
} else {
temp.next = list2;
list2 = list2.next;
}
//temp节点始终指向末尾节点 每次将一个节点添加到合并链表后,temp会移动到新的末尾节点
temp = temp.next;
}
temp.next = list1 == null ? list2 : list1;
return res.next;
}
题目:两数相加
原题链接:两数相加
题解
思路是通过遍历两个链表,计算对应节点值与进位的和,处理进位并构建新链表,最后返回不含虚拟头节点的结果链表。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode dummy = new ListNode(0);
ListNode temp = dummy;
while (l1 != null || l2 != null) {
// 简化写法
int val1 = (l1 != null) ? l1.val : 0;
int val2 = (l2 != null) ? l2.val : 0;
int sum = val1 + val2 + carry;
carry = sum / 10;
temp.next = new ListNode(sum % 10);
temp = temp.next;
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
if (carry > 0) {
temp.next = new ListNode(carry);
}
return dummy.next;
}
原文地址:https://blog.csdn.net/m0_64289188/article/details/140217896
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!