一、单链表
1.单链表的节点结构
2.反转单向和双向链表
2.1 反转单向
package leetcode.链表;
/**
* @author lin
* @creat 2022--12--12:50
*
* https://leetcode.cn/problems/reverse-linked-list/
*/
public class $_206反转链表 {
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;
}
}
//方法一:使用递归的方式进行反转
public ListNode reverse(ListNode pre,ListNode cur){
if (cur==null){//终止遍历的条件就是cur==null
return pre;//返回新链表的头节点
}
ListNode temp=null;
temp=cur.next;//记录下一个节点的位置
//改变链表的方向
cur.next=pre;
//更新pre和cur的位置
//pre=cur;
//cur=temp;
return reverse(cur,temp);
}
public ListNode reverseList(ListNode head) {
//这里为什么传入的是null,head
//因为初始化pre是指向头节点的前面,cur指向头节点
return reverse(null,head);
}
//方法二:使用双指针
public ListNode reverseList2(ListNode head){
ListNode pre=null;
ListNode cur=head;
ListNode temp=cur.next;
while (cur!=null){
temp=cur.next;//保存下一个节点,要不然找不到
//将链表方向进行改变
cur.next=pre;
//将cur赋值给pre
pre=cur;
//将temp赋值给cur
cur=temp;
}
//返回新链表的头节点,此时cur指向null
return pre;
}
}
2.2反转双向链表
/**
* P104 T31 双向链表 相当于简化版的Linkedlist
* 主要实现了从表头,表尾插入一个结点,在指定结点之前或之后插入一个结点,
* 从表头,表尾删除一个结点,删除指定结点
* 指定索引返回结点
*
*
* 测试通过;
*
* @author he
*
*/
class DoubleNode<T> {
private int N;// 记录元素个数
private Node first;// 头结点
private Node last;// 尾结点
private class Node {
T item;
Node perv;// 前一个结点
Node next;// 后一个结点
@Override
public String toString() {
// TODO Auto-generated method stub
return item + "";
}
}
// 根据索引获取结点
public Node getNode(int index) {
if (index < 0 || index >= N) {
throw new IndexOutOfBoundsException();
}
Node node = first;
for (int i = 0; i < index; i++) {
node = node.next;
}
return node;
}
// 判断是否为空
public boolean isEmpty() {
return N == 0;
}
// 元素个数
public int size() {
return N;
}
// 表头插入结点
public void pushFirst(T item) {
Node oldfirst = first;
first = new Node();
first.item = item;
if (isEmpty()) {
last = first;
} else {
first.next = oldfirst;
oldfirst.perv = first;
}
N++;
}
// 在指定结点前添加新结点
public void pushBefore(Node newnode, Node node) {
newnode.next = node;
newnode.perv = node.perv;
newnode.next.perv = newnode;
// 防止在头结点前面插入新结点
if (newnode.perv != null) {
newnode.perv.next = newnode;
}
N++;
}
// 在指定索引前插入新结点
public void pushBeforeOfIndex(T item, int index) {
Node node = getNode(index);
Node newnode = new Node();
newnode.item = item;
pushBefore(newnode, node);
}
// 从表尾插入
public void pushLast(T item) {
Node oldlast = last;
last = new Node();
last.item = item;
last.next = null;
if (isEmpty()) {
first = last;
} else {
oldlast.next = last;
last.perv = oldlast;
}
N++;
}
// 在指定结点后添加新结点
public void pushAfter(Node newnode, Node node) {
newnode.perv = node;
newnode.next = node.next;
newnode.perv.next = newnode;
// 防止在尾结点之后插入新结点
if (newnode.next != null) {
newnode.next.perv = newnode;
}
N++;
}
// 在指定索引之后添加结点
public void pushAfterOfIndex(T item, int index) {
Node newnode = new Node();
newnode.item = item;
Node node = getNode(index);
pushAfter(newnode, node);
}
// 从表头删除一个结点
public void popFirst() {
first = first.next;
if (first != null) {
first.perv = null;
}
N--;
}
// 从表为删除一个结点
public void popLast() {
last.perv.next = null;
last.perv = null;
N--;
}
// 删除指定的结点
public void pop(Node node) {
node.perv.next = node.next;
node.next.perv = node.perv;
node.perv = null;
node.next = null;
N--;
}
// 删除指定索引的结点
public void popOfIndex(int index) {
if (index == 0) {
popFirst();
} else if (index == N - 1) {
popLast();
} else {
Node node = getNode(index);
pop(node);
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
Node node = first;
for (int i = 0; i < N; i++) {
sb.append("[");
sb.append(node);
sb.append("]");
sb.append(",");
node = node.next;
}
return sb.toString();
}
}
}
3.练习
1.打印两个有序的链表的公共部分
2.思路
1.都从0开始
2.谁小谁移动,相等打印
3.相等后两个一起移动
4.面试中技巧
5.判断是否为会回文结构
1.快慢指针
在链表中,维持两个指针,跳跃速度不同(A跳一步,B就跳两步)。当B到达终点的时候,A到达中间位置。
2.思路
3.代码实现【不使用额外空间】
// need O(1) extra space
public static boolean isPalindrome3(Node head) {
if (head == null || head.next == null) {
return true;
}
Node n1 = head;//慢指针
Node n2 = head;//快指针
//快慢指针找末尾和中点
while (n2.next != null && n2.next.next != null) { // find mid node
n1 = n1.next; // n1 -> mid
n2 = n2.next.next; // n2 -> end
}
n2 = n1.next; // n2 -> right part first node
n1.next = null; // mid.next -> null
Node n3 = null;//用于记录n2原本的下一个node
//右半部分逆序
while (n2 != null) { // right part convert
n3 = n2.next; // n3 -> save next node,保留未改变的链表
n2.next = n1; // next of right node convert,改变链表指向
//n1,n2两个指针完成改变指向操作后,同时右移,准备下一个元素的链表指向逆序
n1 = n2; // n1 move
n2 = n3; // n2 move
}
n3 = n1; // n3 -> save last node
n2 = head;// n2 -> left first node
boolean res = true;
while (n1 != null && n2 != null) { // check palindrome
//每走一步,都验证
if (n1.value != n2.value) {
res = false;
break;
}
//n1,n2从中间开始走
n1 = n1.next; // left to mid
n2 = n2.next; // right to mid
}
n1 = n3.next;
n3.next = null;
//最后将逆序的链表变回来
while (n1 != null) { // recover list
n2 = n1.next;
n1.next = n3;
n3 = n1;
n1 = n2;
}
return res;
}
6.按某值划分单向链表
1.思路
2.代码实现
public static Node listPartition2(Node head, int pivot) {
Node sH = null; // small head
Node sT = null; // small tail
Node eH = null; // equal head
Node eT = null; // equal tail
Node bH = null; // big head
Node bT = null; // big tail
Node next = null; // save next node
// every node distributed to three lists
while (head != null) {
next = head.next;
head.next = null;
if (head.value < pivot) {
if (sH == null) {
sH = head;
sT = 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 (bH == null) {
bH = head;
bT = head;
} else {
bT.next = head;
bT = head;
}
}
head = next;
}
// small and equal reconnect
if (sT != null) {
sT.next = eH;
eT = eT == null ? sT : eT;
}
// all reconnect
if (eT != null) {
eT.next = bH;
}
return sH != null ? sH : eH != null ? eH : bH;
}
7.复制含有随机指针节点的链表
做法1:第一次遍历旧链表,使用哈希map,key为旧链表,value为新链表,新链表只是单纯地串起来并拷贝int value值,rand没有设置;第二次遍历旧链表,调用key-value,设置rand node。
做法2:第一次遍历旧链表,不用哈希map,在旧map中,插入克隆node,拷贝int value值;第二次遍历链表,一对一对处理,设置rand node;第三次遍历,把旧节点删除。省去了hashmap的空间。
8.两个单链表相交
思路
情况1:两个链表都无环
情况1:2个链表都是无环,只可能是2条线,或者y型线,不可能是x型,x型就是节点处next指针指向2个地方,这是不可能的。2个链表如果相交,那么他们end端一定是地址一样的,2个链表都遍历。如果相交,要找到节点处,长的列表先走len(long)-len(short)步,然后一起走,一定会在交点处相遇。
情况1:做题步骤
1.先对两个链表分别求出end节点和length
2.然后判断两个链表的end是否是指向同一个地址
3.如果是指向同一个地址,则先让长链表走【length长-length短】步,然后再让长的链表和短链表同时继续走。
情况1: 代码实现
//两个有环链表。返回第一个相交节点,如果不想交返回null
//loop1,loop2分别为2个链表的环入口处节点
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {//如果入环节点相同,是情况3-2
cur1 = head1;
cur2 = head2;
//此时n:表示链表1长度减去链表2长度的值
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
//谁长,谁的头变成cur1
cur1 = n > 0 ? head1 : head2;
//谁短,谁的头变成cur2
cur2 = cur1 == head1 ? head2 : head1;
//取绝对值
n = Math.abs(n);
//长链表先走【长链表-短链表】步
while (n != 0) {
n--;
cur1 = cur1.next;
}
//然后长链表和短链表再一起走
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
//再一次相遇表示相交节点
return cur1;
} else {//如果入环节点不同,是情况3-1或3-3
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;//情况3-3
}
cur1 = cur1.next;
}
return null;//情况3-1
}
}
情况二:一个链表有环,一个链表无环
一个为无环,一个有环,那么必然不想交;【只要一个链表有环,则另一个链表接进去后,环也会成为它后面的一部分,所以必定有环】
情况三:两个链表都有环
情况3:2个都是有环,又分3种情况:
情况3-1:2个不同的有环;
情况3-2:入环节点是同一个,最好判断,分别找到入环节点,如果入环节点不同就是情况3-1或者3-3,如果入环节点相同,就使用上面的无环代码去找相交节点;
情况3-3:入环节点不是同一个;让loop1继续走,在走回自己之前,判断会不会遇到loop2这个入口节点,遇到就是情况3-3,没有就是情况3-1;
//两个有环链表。返回第一个相交节点,如果不想交返回null
//loop1,loop2分别为2个链表的环入口处节点
public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
Node cur1 = null;
Node cur2 = null;
if (loop1 == loop2) {//如果入环节点相同,是情况3-2
cur1 = head1;
cur2 = head2;
int n = 0;
while (cur1 != loop1) {
n++;
cur1 = cur1.next;
}
while (cur2 != loop2) {
n--;
cur2 = cur2.next;
}
cur1 = n > 0 ? head1 : head2;
cur2 = cur1 == head1 ? head2 : head1;
n = Math.abs(n);
while (n != 0) {
n--;
cur1 = cur1.next;
}
while (cur1 != cur2) {
cur1 = cur1.next;
cur2 = cur2.next;
}
return cur1;
} else {//如果入环节点不同,是情况3-1或3-3
cur1 = loop1.next;
while (cur1 != loop1) {
if (cur1 == loop2) {
return loop1;//情况3-3
}
cur1 = cur1.next;
}
return null;//情况3-1
}
}
9.判断链表中是否有环
如果快慢指针的next不会指向null,则表示有环
法一:使用额外空间---哈希表
遍历链表依次存入哈希表,直到节点已经出现在哈希表
法二:不使用额外空间----快慢指针
快慢指针从同一个起点出发,快指针走2步,慢指针走1步
查看入环节点
如果链表中有环,快慢指针肯定会相遇,当相遇的时候,快指针回到起点,慢指针在原地,一起往前走每次走一步,再次相遇既是环入口节点
//获取环的入口
public static Node getLoopNode(Node head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
Node n1 = head.next; // n1 -> slow
Node n2 = head.next.next; // n2 -> fast
while (n1 != n2) {
//判断快指针是否走完
if (n2.next == null || n2.next.next == null) {
return null;
}
n2 = n2.next.next;
n1 = n1.next;
}
n2 = head; // n2 -> walk again from head
while (n1 != n2) {
n1 = n1.next;
n2 = n2.next;
}
//再一次相遇的时候,就是入环节点
return n1;
}