单链表的基本操作：
- 合并两个有序链表
- 合并k个有序链表
- 寻找单链表的中点
- 寻找单链表中的第k个节点
- 判断单链表是否包含环并找出环起点
- 判断两个单链表是否相交并找出交点
学习目标
- 复习Day1内容
- 寻找单链表的中点
- 寻找单链表中的第k个节点
学习内容 单链表操作
- 1. 创建链表类及节点： 在单链表中，我们首先要定义链表中最基础的节点元素。如上图所示，节点中包括两个属性，指针next和数据data。同时，我们可以在创建时定义链表的头节点、尾节点和链表长度。
//创建一个链表的类
class ListNode{
int val; //数值 data
ListNode next; // 结点 node
ListNode(int x){//可以定义一个有参构造方法，也可以定义一个无参构造方法
val = x;
}
}
- 2. 判断链表是否为空： 判断链表为空的三种条件分别为：
- 带头节点的单链表：head->next==NULL
- 带头节点的循环链表：head->next==head
- 不带头节点的单链表：head==NULL
public boolean isEmpty() {
return isEmpty(first);
}
public static boolean isEmpty(Node head) {
return head == null;
}
- 3. 返回链表的长度： 遍历链表，直至它为空
public int size() {
return size(first);
}
public static int size(Node head) {
Node temp = head;
int size = 0;
while (temp != null) {
size++;
temp = temp.next;
}
return size;
}
- 4. 正向遍历链表： 正向遍历链表，直至链表为空
public void printList() {
Node temp = first;
while (temp != null) {
System.out.println(temp.item);
temp = temp.next;
}
}
- 5. 反向遍历链表： 反向遍历链表，直至到第一个节点的head
public void printListReverse() {
Node temp = first;
printListReverse(temp);
}
private void printListReverse(Node e) {
if (e != null) {
printListReverse(e.next);
System.out.println(e.item);
}
}
- 6. 链表头部添加节点： 如果头部节点为空，新加节点就是头节点；弱国头部节点不为空，则新加节点的next就是头节点，并且将头节点设置为新加节点。
public void addFirst(E e) {
Node temp = first;
final Node newNode = new Node(e, null);
if (temp == null) {
first = newNode;
}
else {
newNode.next = temp;
first = newNode;
}
}
- 7. 链表尾部添加节点： 直接找到最后一个节点，添加到最后一个节点的next。如果链表长度为0，直接令first为新插入节点。
public void addLast(E e) {
Node temp = first;
Node newNode = new Node(e, null);
if (temp == null) {
first = newNode;
}
else {
while (temp.next != null) {
temp = temp.next;
}
temp.next = newNode;
}
}
- 8. 指定值的后面添加节点： 如果链表中已经有了重复的值，以排在最前面的为准。如果插入成功，则返回true；如果插入失败，则返回false；如果链表是空的，直接返回false。
public boolean addBefore(E aimValue, E insertValue) {
Node temp = first;
if (temp == null) {
return false;
}
else {
while (temp != null) {
if (temp.item.equals(insertValue)) {
Node newNode = new Node(aimValue, null);
newNode.next = temp.next;
temp.next = newNode;
return true;
}
else {
temp = temp.next;
}
}
return false;
}
}
- 9. 所有指定值的后面添加节点： 如果头节点为空，直接返回0；如果头节点不为空，那么链表中所有指定值的后面都添加节点，并返回插入值的个数。
public int addBeforeAll(E aimValue, E insertValue) {
// 插入值的个数
int count = 0;
if (first == null) {
return 0;
}
else {
Node temp = first;
while (temp != null) {
if (temp.item.equals(aimValue)) {
Node newNode = new Node<>(insertValue, null);
newNode.next = temp.next;
temp.next = newNode;
count++;
// 由于是在temp后面加了一个指定值，所以，要令temp = temp.next.next;
temp = temp.next.next;
}
else {
temp = temp.next;
}
}
}
return count;
}
学习时间
2022年5月25日
- 下午3点-下午5点
- 晚上8点-晚上9点
学习产出
- 本文档链表基础知识和基础操作
- 力扣19题，删除链表的倒数第N个节点
- 力扣876题，链表的中间节点
今日刷题
19.删除链表的倒数第N个节点
-
从前往后寻找单链表的第 k 个节点很简单，一个 for 循环遍历过去就找到了，但是如何寻找从后往前数的第 k 个节点呢？那你可能说，假设链表有 n 个节点，倒数第 k 个节点就是正数第 n - k + 1 个节点，不也是一个 for 循环的事儿吗？
-
是的，但是算法题一般只给你一个 ListNode 头结点代表一条单链表，你不能直接得出这条链表的长度 n，而需要先遍历一遍链表算出 n 的值，然后再遍历链表计算第 n - k + 1 个节点。也就是说，这个解法需要遍历两次链表才能得到出倒数第 k 个节点。那么，我们能不能只遍历一次链表，就算出倒数第 k 个节点？可以做到的，如果是面试问到这道题，面试官肯定也是希望你给出只需遍历一次链表的解法。
-
这个解法就比较巧妙了，假设 k = 2，思路如下：
首先，我们先让一个指针 p1 指向链表的头节点 head，然后走 k 步：
现在的 p1，只要再走 n - k 步，就能走到链表末尾的空指针了对吧？
趁这个时候，再用一个指针 p2 指向链表头节点 head：
接下来就很显然了，让 p1 和 p2 同时向前走，p1 走到链表末尾的空指针时前进了 n - k 步，p2 也从 head 开始前进了 n - k 步，停留在第 n - k + 1 个节点上，即恰好停链表的倒数第 k 个节点上：
这样，只遍历了一次链表，就获得了倒数第 k 个节点 p2。
上述逻辑的代码如下
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}
当然，如果用 big O 表示法来计算时间复杂度，无论遍历一次链表和遍历两次链表的时间复杂度都是 O(N)，但上述这个算法更有技巧性。
接下来，正式看第19题。
- tips: 这个逻辑就很简单了，要删除倒数第 n 个节点，就得获得倒数第 n + 1 个节点的引用，可以用我们实现的 findFromEnd 来操作。
- tips: 不过注意我们又使用了虚拟头结点的技巧，也是为了防止出现空指针的情况，比如说链表总共有 5 个节点，题目就让你删除倒数第 5 个节点，也就是第一个节点，那按照算法逻辑，应该首先找到倒数第 6 个节点。但第一个节点前面已经没有节点了，这就会出错。
- tips: 但有了我们虚拟节点 dummy 的存在，就避免了这个问题，能够对这种情况进行正确的删除。
class Solution {
// 主函数
public ListNode removeNthFromEnd(ListNode head, int n) {
// 虚拟头结点
ListNode dummy = new ListNode(-1);
dummy.next = head;
// 删除倒数第 n 个，要先找倒数第 n + 1 个节点
ListNode x = findFromEnd(dummy, n + 1);
// 删掉倒数第 n 个节点
x.next = x.next.next;
return dummy.next;
}
// 返回链表的倒数第 k 个节点
ListNode findFromEnd(ListNode head, int k) {
ListNode p1 = head;
// p1 先走 k 步
for (int i = 0; i < k; i++) {
p1 = p1.next;
}
ListNode p2 = head;
// p1 和 p2 同时走 n - k 步
while (p1 != null) {
p2 = p2.next;
p1 = p1.next;
}
// p2 现在指向第 n - k 个节点
return p2;
}
}
876.链表的中间节点
- 问题的关键也在于我们无法直接得到单链表的长度 n，常规方法也是先遍历链表计算 n，再遍历一次得到第 n / 2 个节点，也就是中间节点。
- 如果想一次遍历就得到中间节点，也需要耍点小聪明，使用「快慢指针」的技巧：我们让两个指针 slow 和 fast 分别指向链表头结点 head。每当慢指针 slow 前进一步，快指针 fast 就前进两步，这样，当 fast 走到链表末尾时，slow 就指向了链表中点。
- 需要注意的是，如果链表长度为偶数，也就是说中点有两个的时候，我们这个解法返回的节点是靠后的那个节点。
class Solution {
public ListNode middleNode(ListNode head) {
// 快慢指针初始化指向 head
ListNode slow = head, fast = head;
// 快指针走到末尾时停止
while (fast != null && fast.next != null) {
// 慢指针走一步，快指针走两步
slow = slow.next;
fast = fast.next.next;
}
// 慢指针指向中点
return slow;
}
}
