文章目录
1.链表定义
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 链表定义
*
* @Author sun
* @Create 2024/11/26 13:30
* @Version 1.0
*/
public class ListNode {
// 节点的值
int val;
// 下一个节点
ListNode next;
// 节点的构造
public ListNode(int val) {
this.val = val;
}
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
2.思路
一个单链表节点需要有两个参数，值和指向下一个节点的指针，以及两个构造
2.移除链表元素
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 203. 移除链表元素
*
* @Author sun
* @Create 2024/11/26 13:35
* @Version 1.0
*/
public class T2_2 {
public ListNode removeElements(ListNode head, int val) {
// 构造哨兵节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 使用临时指针循环遍历
ListNode temp = dummy;
while (temp.next != null) {
// 如果需要删除，则进行删除操作
if (temp.next.val == val) {
temp.next = temp.next.next;
} else {
// 如果不需要删除，则移动temp
temp = temp.next;
}
}
// 返回新的头结点
return dummy.next;
}
}
2.思路
使用一个哨兵节点，指向头节点，然后使用临时指针去循环遍历，进行删除操作
3.设计链表
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 707.设计链表
*
* @Author sun
* @Create 2024/11/26 13:50
* @Version 1.0
*/
public class MyLinkedList {
/**
* 值
*/
int val;
/**
* 指向下一个节点的指针
*/
MyLinkedList next;
/**
* 哨兵节点
*/
MyLinkedList dummy;
/**
* 构造器
*
* @param val
*/
private MyLinkedList(int val) {
this.val = val;
}
/**
* 初始化 MyLinkedList 对象
*/
public MyLinkedList() {
// 初始化哨兵节点
dummy = new MyLinkedList(-1);
}
/**
* 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1
*
* @param index
* @return
*/
public int get(int index) {
// 求链表的长度
int len = getLen();
// 下标无效，直接返回
if (index < 0 || index >= len) {
return -1;
} else {
MyLinkedList curr = dummy;
int num = -1;
while (curr.next != null) {
num ++;
// 此时的num，就是下一个元素的下标
if (num == index) {
return curr.next.val;
} else {
curr = curr.next;
}
}
return -1;
}
}
/**
* 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
*
* @param val
*/
public void addAtHead(int val) {
// 构建节点
MyLinkedList node = new MyLinkedList(val);
// 插入到第一个元素之前
node.next = dummy.next;
dummy.next = node;
}
/**
* 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
*
* @param val
*/
public void addAtTail(int val) {
// 构建节点
MyLinkedList node = new MyLinkedList(val);
// 遍历链表
MyLinkedList curr = dummy;
while (curr.next != null) {
curr = curr.next;
}
// 添加节点
curr.next = node;
}
/**
* 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
* 如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
*
* @param index
* @param val
*/
public void addAtIndex(int index, int val) {
int len = getLen();
// 当index比链表的长度更长，就直接返回
if (index > len) {
return;
}
// 当index是链表的长度，那么就插入到链表的末尾
if (index == len) {
addAtTail(val);
} else {
// 其余情况，就插入到该元素之前
// 首先，移动到该元素的前一个位置
MyLinkedList curr = dummy;
int num = -1;
while (curr.next != null) {
num ++;
// 此时的num就代表下一个元素的下标
if (num == index) {
// 如果下一个元素的下标就是index，则插入元素
// 构建节点
MyLinkedList node = new MyLinkedList(val);
// 插入到下一个元素之前
node.next = curr.next;
curr.next = node;
// 直接退出
break;
} else {
// 如果不是，则继续遍历
curr = curr.next;
}
}
}
}
/**
* 求链表的长度
*
* @return
*/
private int getLen() {
int len = 0;
MyLinkedList curr = dummy;
while (curr.next != null) {
curr = curr.next;
len++;
}
return len;
}
/**
* 如果下标有效，则删除链表中下标为 index 的节点。
*
* @param index
*/
public void deleteAtIndex(int index) {
// 求链表的长度
int len = getLen();
// 下标无效，直接返回
if (index < 0 || index >= len) {
return;
}
// 找到指定下标的元素
int num = -1;
MyLinkedList curr = dummy;
while (curr.next != null) {
num ++;
// 此时的num则代表下一个元素的下标，如果满足要求，就直接删除，然后退出
if (num == index) {
// 删除下一个元素，然后退出
curr.next = curr.next.next;
return;
} else {
// 不满足要求就继续遍历
curr = curr.next;
}
}
}
}
2.思路
核心就是设置一个虚拟的头结点，然后使用临时节点进行遍历
4.反转链表
1.答案（递归实现）
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 206. 反转链表
*
* @Author sun
* @Create 2024/11/26 14:27
* @Version 1.0
*/
public class T2_4 {
private ListNode res;
public ListNode reverseList(ListNode head) {
reverse(null, head);
return res;
}
/**
* 函数调用记录状态
*
* @param prev 前一个节点
* @param curr 当前节点
*/
public void reverse(ListNode prev, ListNode curr) {
// 退出条件
if (curr == null) {
res = prev;
return;
} else {
reverse(curr, curr.next);
curr.next = prev;
}
}
}
2.思路
这里使用了递归的思想，用到了核心之一，就是函数调用，记录状态，使用递归分别记录当前节点和前一个节点的状态，从而完成链表的反转
5.两两交换链表中的节点
1.答案（递归实现）
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 24. 两两交换链表中的节点
*
* @Author sun
* @Create 2024/11/26 15:06
* @Version 1.0
*/
public class T2_5 {
public ListNode swapPairs(ListNode head) {
if (head == null) {
return null;
}
if (head.next == null) {
return head;
}
return swap(head.next, head);
}
public ListNode swap(ListNode curr, ListNode prev) {
// 终止条件
if (curr == null) {
return prev;
} else if (curr.next == null) {
// 反转当前这对节点
curr.next = prev;
prev.next = null;
// 然后返回当前节点
return curr;
} else {
ListNode swap = swap(curr.next.next, curr.next);
// 反转当前这对节点
curr.next = prev;
prev.next = swap;
return curr;
}
}
}
2.思路
递归思考的顺序是参数传递状态，然后考虑终止条件，最后考虑返回值。
6.删除链表的倒数第 N 个结点
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 19. 删除链表的倒数第 N 个结点
*
* @Author sun
* @Create 2024/11/26 16:20
* @Version 1.0
*/
public class T2_6 {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 校验合法性
if (n < 1 || n > getLen(head)) {
return null;
}
// 计算倒数第n个是正数的下标
int delete = getLen(head) - n;
// 头节点
ListNode dummy = new ListNode(-1);
dummy.next = head;
ListNode curr = dummy;
int index = -1;
while (curr.next != null) {
index ++;
// 此时的index就是正数的下标，删除并返回头结点
if (index == delete) {
curr.next = curr.next.next;
return dummy.next;
} else {
// 如果不是就移动
curr = curr.next;
}
}
return null;
}
/**
* 返回链表的长度
*
* @param head
* @return
*/
private int getLen(ListNode head) {
int len = 0;
ListNode curr = head;
while (curr != null) {
len++;
curr = curr.next;
}
return len;
}
}
2.思路
首先计算出删除倒数第n个节点其实是删除正数的节点下标，然后就变成了删除指定下标的节点
7.链表相交
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 面试题 02.07. 链表相交
*
* @Author sun
* @Create 2024/11/26 16:46
* @Version 1.0
*/
public class T2_7 {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
// 分别计算两个链表长度
int lenA = getLen(headA);
int lenB = getLen(headB);
ListNode currA = headA;
ListNode currB = headB;
// 根据长度不同，做不同的处理
if (lenA > lenB) {
int difference = lenA - lenB;
// A移动这么长
while (difference > 0) {
currA = currA.next;
difference --;
}
} else if (lenA < lenB) {
int difference = lenB - lenA;
// B移动这么长
while (difference > 0) {
currB = currB.next;
difference --;
}
}
// 长度相同则不需要处理
// A、B同时移动，直到相遇，或者到了最后
while (currA != null && currB != null) {
// 判断是否相遇
if (currA == currB) {
return currA;
}
currA = currA.next;
currB = currB.next;
}
// 如果退出循环了，就说明没有相遇
return null;
}
/**
* 计算链表长度
*
* @param head
* @return
*/
private int getLen(ListNode head) {
ListNode curr = head;
int len = 0;
while (curr != null) {
len ++;
curr = curr.next;
}
return len;
}
}
2.思路
首先计算两个链表的长度，根据长度不同，让长的那个链表移动差值的长度，然后两个指针同时移动，然后就可以判断是否相遇了
8.环形链表 II
1.答案
package com.sunxiansheng.suanfa.daimasuixianglu;
/**
* Description: 142. 环形链表 II
*
* @Author sun
* @Create 2024/11/27 10:28
* @Version 1.0
*/
public class T2_8 {
public ListNode detectCycle(ListNode head) {
// 快慢指针
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
// 快指针移动两步，慢指针移动一步
fast = fast.next.next;
slow = slow.next;
// 判断是否相遇
if (fast == slow) {
// 这样只能代表有环，让slow指向head，然后再一起走，再次相遇即是相遇起始节点
slow = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
return null;
}
}
2.思路
使用快慢指针，只要相遇了，就说明一定有环，但是如果想要找到环的起始点，需要让slow指向head，然后一起移动，直至相遇