链表部分:
链表部分:
[图片上传失败...(image-b2bb7d-1649069467758)]
1.反转单双链表
//迭代的方式
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
//2.反转链表的递归方式
private ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode node = reverse(head.next);
head.next.next = head;
head.next = null;
return node;
}
2.打印俩有序链表的公共部分
方法论:
时间复杂度最低即可
1.额外的数据结构记录
2.快慢指针的方式
进阶
1.回文链表
笔试版:
1.借助栈
2.快慢指针
整个流程可以分为以下五个步骤：
- 找到前半部分链表的尾节点。
- 反转后半部分链表。
- 判断是否回文。
- 恢复链表。
- 返回结果。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public boolean isPalindrome(ListNode head) {
if (head == null) {
return true;
}
// 找到前半部分链表的尾节点并反转后半部分链表
ListNode firstHalfEnd = endOfFirstHalf(head);
// ListNode secondHalfStart = reverseList(firstHalfEnd.next);
ListNode secondHalfStart = reverse(firstHalfEnd.next);
// 3.判断是否回文
ListNode p1 = head;
ListNode p2 = secondHalfStart;
boolean result = true;
while (result && p2 != null) {
if (p1.val != p2.val) {
result = false;
}
p1 = p1.next;
p2 = p2.next;
}
// 4.还原链表并返回结果
// firstHalfEnd.next = reverseList(secondHalfStart);
firstHalfEnd.next = reverse(secondHalfStart);
return result;
}
//2.反转后半部分链表。
private ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode curr = head;
while (curr != null) {
ListNode nextTemp = curr.next;
curr.next = prev;
prev = curr;
curr = nextTemp;
}
return prev;
}
//2.反转链表的递归方式
private ListNode reverse(ListNode head){
if(head == null || head.next == null){
return head;
}
ListNode node = reverse(head.next);
head.next.next = head;
head.next = null;
return node;
}
//1.找到前半部分链表的尾节点。利用快慢指针。
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
2.将单链表按照值划分为左边小,右边大,中间相等的形式
数组Node[N]
玩快排
面试:有限的变量去做
[图片上传失败...(image-76ef68-1649069467758)]
[图片上传失败...(image-c32a99-1649069467758)]
存在 5 既没有小的也没有等的也没有大的所以我们要判断
防止空指针加入报错
public static Node listPivot (Node head,int pivot){
//六个变量保持有序且符合题意
Node SH = null;//small head
Node ST = null;//small tail
Node ET = null;//equal head
Node EH = null;//qual tail
Node MH = null;//big head
Node MT = null;//big tail
Node next = null;//save nexxt node
while(head != null){
//互指用来保存首部尾部
next = head.next;
head.next = null;
if(head.value < pivot){
//如果当前最小头是新的节点。那么我们初始化最小头和最小尾都指向该链表的头。
if(SH == null){
SH = head;
ST = head;
}
//如果当前节点不是最新的话。把老的Next指向当前节点head。 NBA。把head作为新的最小头的尾巴。
}else{
ST.next = head;
ST = head;
}else if(head.value = pivot){
if(EH == null){
EH = head;
ET = head;
}
}else{
ET.next = head;
ET = head;
} else if(head.value > pivot){
if(MH == null){
MH = head;
MT = head;
}
}else{
MH.next = head;
MT = head;
}
head = head.next;
}
//链接:
// ST -> EH 和 ET -> MH;
//充分讨论有没有大于下雨区域
if(ST != null){ //如果有小于的区域
ST.next = EH;
ET = ET == null ? ST : ET;//谁去来凝结大的区域的头谁就变成eT
}
if(ET != null){
ET.next = MH;
}
//**************
//最后定返回头节点
//**************
return SH != null ? SH :(EH != null ? EH : MH);
}
}
3.复制含有随机指针节点的链表
[图片上传失败...(image-82b98b-1649069467758)]
Hash表来存储
<key,value> 老节点对应的新节点
[图片上传失败...(image-e21780-1649069467758)]
不用HashMap
1.跟随设置,复制节点不要设置
[图片上传失败...(image-1fcb63-1649069467758)]
2.跟随的next位置设置
[图片上传失败...(image-28d6df-1649069467758)]
3.分离出来
public static Node copyListWithRand(Node head){
if(head == null){
return null;
}
Node cur = head;
Node next = null;
//1. 在每一个原始节点后面跟随设置他的copy节点。例如1 - > 1"
while(cur !=null){
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
//重置car为head即将当前的节点，作为该链表的头。再来一次便利。
cur = head;
Node curCopy = null;
//2.按照该链表原来的方式设置。它的Next和Random。
while(cur != null){
next = cur.next.next;
curCopy = cur.next;
curCopy.rand = cur.rand != null ? cur.rand.next : null;
cur = next;
}
Node res = head.next;
cur = head;
//将拷贝节点全部切分出去。
while(cur != null){
next = cur.next.next;
curCopy = cur.next;
cur.next = next;
curCopy.next = next != null? next.next : null;
cur = next;
}
return res;
}
4.单链表相交
[图片上传失败...(image-24cb9e-1649069467758)]
利用HashSet来遍历
有没有重复
[图片上传失败...(image-b6a312-1649069467758)]
快慢指针经典
相遇后:
快指针回到head 以后每次走一步,就一定会在入口相遇
链表题目练习
链表
提纲
链表相关的核心点
- null 异常处理
- dummy node 哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点
基本操作
链表删除
删除排序链表中的重复元素
给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。
public ListNode deleteDuplicates(ListNode head) {
ListNode p = head;
while (p != null) {
// 全部删除完再移动到下一个元素
while (p.next != null && p.val == p.next.val) {
p.next = p.next.next;
}
p = p.next;
}
return head;
}
删除排序链表中的重复元素 II
给定一个排序链表，删除所有含有重复数字的节点，只保留原始链表中 没有重复出现的数字。
思路：链表头结点可能被删除，所以用 dummy node 辅助删除
public ListNode deleteDuplicates(ListNode head) {
if (head == null) {
return null;
}
ListNode newHead = new ListNode(-1, head);
ListNode p = newHead;
int n = 0;
while (p.next != null && p.next.next != null) {
if (p.next.val == p.next.next.val) {
// 记录已经删除的值，用于后续节点判断
n = p.next.val;
while (p.next != null && p.next.val == n) {
p.next = p.next.next;
}
} else {
p = p.next;
}
}
return newHead.next;
}
注意点
- A->B->C 删除 B，A.next = C
- 删除用一个 Dummy Node 节点辅助（允许头节点可变）
- 访问 X.next 、X.value 一定要保证 X != nil
链表反转
反转链表
反转一个单链表。
思路：用一个 prev 节点保存向前指针，temp 保存向后的临时指针
public ListNode reverseList(ListNode head) {
ListNode pre = null, p = head;
while (p != null) {
// 保存当前head.Next节点，防止重新赋值后被覆盖
// 一轮之后状态：nil<-1 2->3->4
// prev p
ListNode temp = p.next;
p.next = pre;
// pre 移动
pre = p;
// p 移动
p = temp;
}
return pre;
}
反转链表 II
反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
思路：先遍历到 m 处，翻转，再拼接后续，注意指针处理
public ListNode reverseBetween(ListNode head, int m, int n) {
// 思路：先遍历到m处，翻转，再拼接后续，注意指针处理
// 输入: 1->2->3->4->5->null, m = 2, n = 4
ListNode newHead = new ListNode(0, head);
ListNode p = newHead;
// 最开始：0(p)->1->2->3->4->5->null
for (int i = 0; i < m-1; i++) {
p = p.next;
}
// 遍历之后： 0->1(p)->2(cur)->3->4->5->null
ListNode pre = null;
ListNode cur = p.next;
for (int i = m; i <= n; i++) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 循环结束：0->1(p)->2->null 5(cur)->null 4(pre)->3->2->null
p.next.next = cur;
p.next = pre;
return newHead.next;
}
链表合并
合并两个有序链表
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：通过 dummy node 链表，连接各个元素
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode p = head;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
// 连接未处理完节点
p.next = l1 == null ? l2 : l1;
return head.next;
}
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
思路：使用分治的方法两个两个地合并链表
public ListNode mergeKLists(ListNode[] lists) {
return merge(lists, 0, lists.length - 1);
}
public ListNode merge(ListNode[] lists, int begin, int end) {
if (begin == end) return lists[begin];
if (begin > end) return null;
int mid = (begin + end) >> 1;
return mergeTwoLists(merge(lists, begin, mid), merge(lists, mid + 1, end));
}
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
// 同上
}
快慢指针
链表中点
使用两个指针变量，慢指针每次前进一步，快指针每次前进两步。这样当快指针到达链表末尾时，慢指针恰好在链表的中间位置。要注意链表长度为偶数的情况。
给定一个头结点为 head 的非空单链表，返回链表的中间结点。
如果有两个中间结点，则返回第二个中间结点。
public ListNode middleNode(ListNode head) {
ListNode p = head;
ListNode q = head;
while (q != null && q.next != null) {
p = p.next;
q = q.next.next;
}
return p;
}
重排链表
143. 重排链表
给定一个单链表 L：L0→L1→…→Ln-1→Ln ，将其重新排列后变为： L0→Ln→L1→Ln-1→L2→Ln-2→…
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
public void reorderList(ListNode head) {
if (head == null || head.next == null) return;
// 通过快慢指针找中点
ListNode slow = head, fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode p = head;
// 反转链表
ListNode q = reverseList(slow.next);
slow.next = null;
while (p != null && q != null) {
ListNode qNext = q.next;
q.next = p.next;
p.next = q;
p = q.next;
q = qNext;
}
}
回文链表
请判断一个链表是否为回文链表。
public boolean isPalindrome(ListNode head) {
// fast如果初始化为head.Next则中点在slow.Next
// fast初始化为head,则中点在slow
ListNode slow = head, fast = head, pre = null;
// 这里顺便做了反转链表的操作
while (fast != null && fast.next != null) {
fast = fast.next.next;
ListNode next = slow.next;
slow.next = pre;
pre = slow;
slow = next;
}
if (fast != null){
slow = slow.next;
}
// 与另一半链表依次比较
while (slow != null) {
if (slow.val != pre.val) return false;
slow = slow.next;
pre = pre.next;
}
return true;
}
结构判断
环形链表
给定一个链表，判断链表中是否有环。
如果链表中存在环，则返回
true。 否则，返回false。
思路：快慢指针，快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减 1
[图片上传失败...(image-8b9f58-1649069467758)]
public boolean hasCycle(ListNode head) {
ListNode p = head, q = head;
// 思路：快慢指针 快慢指针相同则有环，证明：如果有环每走一步快慢指针距离会减1
while (p != null && q != null && q.next != null) {
p = p.next;
q = q.next.next;
// 比较指针是否相等（不要使用val比较）
if (p == q) {
return true;
}
}
return false;
}
环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回
null。
思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点
[图片上传失败...(image-b266f5-1649069467758)]
public ListNode detectCycle(ListNode head) {
// 思路：快慢指针，快慢相遇之后，慢指针回到头，快慢指针步调一致一起移动，相遇点即为入环点
ListNode p = head, q = head;
while (p != null && q != null && q.next != null) {
p = p.next;
q = q.next.next;
if (p == q) {
// 指针重新从头开始移动
ListNode m = head;
// 比较指针对象（不要比对指针Val值）
while (m != p) {
m = m.next;
p = p.next;
}
return p;
}
}
return null;
}
其他
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。(尝试使用一趟扫描实现)
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode newHead = new ListNode(0, head);
ListNode p1 = newHead;
ListNode p2 = newHead;
// 提前前进n个位置
while (n >= 0) {
p2 = p2.next;
n--;
}
while (p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
p1.next = p1.next.next;
return newHead.next;
}
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的 深拷贝。
思路：1、hash 表存储指针，2、复制节点跟在原节点后面
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// 复制节点，紧挨到到后面
// 1->2->3 ==> 1->1'->2->2'->3->3'
Node cur = head;
while (cur != null) {
Node cloneNode = new Node(cur.val);
cloneNode.next = cur.next;
Node temp = cur.next;
cur.next = cloneNode;
cur = temp;
}
// 处理random指针
cur = head;
while (cur != null) {
if (cur.random != null) {
cur.next.random = cur.random.next;
}
cur = cur.next.next;
}
// 分离两个链表
cur = head;
Node cloneHead = cur.next;
while (cur != null && cur.next != null) {
Node temp = cur.next;
cur.next = cur.next.next;
cur = temp;
}
// 原始链表头：head 1->2->3
// 克隆的链表头：cloneHead 1'->2'->3'
return cloneHead;
}
总结
链表必须要掌握的一些点，通过下面练习题，基本大部分的链表类的题目都是手到擒来~
- null 异常处理
- dummy node 哑巴节点
- 快慢指针
- 插入一个节点到排序链表
- 从一个链表中移除一个节点
- 翻转链表
- 合并两个链表
- 找到链表的中间节点
- 链表的末尾指针最后指向null
