Summary
- LinkedList
- 移除链表元素 203. Remove Linked List Elements💚
- 创建链表 707. Design Linked List🧡
- 翻转链表 206. Reverse Linked List💚
- 两两交换链表中的节点 24. Swap Nodes in Pairs🧡
- 删除链表的倒数第N个节点 19. Remove Nth Node From End of List🧡
- 链表相交 160. Intersection of Two Linked Lists💚
- 环形链表
8.1 141. Linked List Cycle 💚
8.2 142. Linked List Cycle II 🧡
1. LinkedList
1. 单链表
链表是一种通过指针串联在一起的线性结构，每一个节点由两部分组成，一个是数据域一个是指针域（存放指向下一个节点的指针），最后一个节点的指针域指向null（空指针的意思）。
链接的入口节点称为链表的头结点也就是head。
2. 双链表
双链表：每一个节点有两个指针域，一个指向下一个节点，一个指向上一个节点。
双链表 既可以向前查询也可以向后查询。
3. 循环链表
链表首尾相连。
循环链表可以用来解决约瑟夫环问题。
4. 链表的储存方式
数组是在内存中是连续分布的，但是链表在内存中可不是连续分布的。
链表是通过指针域的指针链接在内存中各个节点。
所以链表中的节点在内存中不是连续分布的 ，而是散乱分布在内存中的某地址上，分配机制取决于操作系统的内存管理。
5. 链表定义
public class ListNode {
// 结点的值
int val;
// 下一个结点
ListNode next;
// 节点的构造函数(无参)
public ListNode() {
}
// 节点的构造函数(有一个参数)
public ListNode(int val) {
this.val = val;
}
// 节点的构造函数(有两个参数)
public ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
6. 性能分析
数组在定义的时候，长度就是固定的，如果想改动数组的长度，就需要重新定义一个新的数组。(长度不确定时，可以使用ArrayList)
链表的长度可以是不固定的，并且可以动态增删， 适合数据量不固定，频繁增删，较少查询的场景。
2. 移除链表元素 203. Remove Linked List Elements
虚拟头节点：移除头结点和移除其他节点的操作是不一样的，因为链表的其他节点都是通过前一个节点来移除当前节点，而头结点没有前一个节点。
所以为了操作方便和统一，设置一个虚拟头结点。
return 头结点的时候，别忘了 return dummyNode.next， 这才是新的头结点
class Solution {
public ListNode removeElements(ListNode head, int val) {
if(head == null){
return head;
}
ListNode dummy = new ListNode(-1, head);
ListNode pre = dummy;
ListNode cur = head;
while(cur != null){
if(cur.val == val){
pre.next = cur.next;
}else{
pre = cur;
}
cur = cur.next;
}
return dummy.next;
}
}
3. 创建链表 707. Design Linked List
class ListNode{
int val;
ListNode next;
ListNode (){};
ListNode (int val){
this.val = val;
}
}
class MyLinkedList {
int size;
ListNode dummy ;
public MyLinkedList() {
size = 0;
dummy = new ListNode(0);
}
public int get(int index) {
if(index < 0 || index >= size){
return -1;
}
ListNode cur = dummy;
for(int i = 0; i <= index; i++){
cur = cur.next;
}
return cur.val;
}
public void addAtHead(int val) {
//顺序很重要，先用插入节点指向head，再用dummy指向插入
addAtIndex(0,val);
}
public void addAtTail(int val) {
addAtIndex(size,val);
}
public void addAtIndex(int index, int val) {
// 在第 index 个节点之前插入一个新节点，例如index为0，那么新插入的节点为链表的新头节点。
// 如果 index 等于链表的长度，则说明是新插入的节点为链表的尾结点
// 如果 index 大于链表的长度，则返回空
if (index > size){
return;
}
if (index < 0){
index = 0;
}
size ++;
ListNode pre = dummy;
for(int i = 0; i < index; i++){
pre = pre.next;
}
ListNode newnode = new ListNode(val);
newnode.next = pre.next;
pre.next = newnode;
}
public void deleteAtIndex(int index) {
if(index < 0 || index >= size){
return;
}
size --;
if (index == 0){
dummy = dummy.next;
return;
}
ListNode pre = dummy;
for (int i = 0; i < index; i++){
pre = pre.next;
}
pre.next = pre.next.next;
}
}
4. 翻转链表 206. Reverse Linked List
4.1 双指针+虚拟头节点：
首先定义一个cur指针，指向头结点，再定义一个pre指针，初始化为null。
然后就要开始反转了，首先要把 cur->next 节点用tmp指针保存一下，也就是保存一下这个节点。
为什么要保存一下这个节点呢，因为接下来要改变 cur->next 的指向了，将cur->next 指向pre ，此时已经反转了第一个节点了。
接下来，就是循环走如下代码逻辑了，继续移动pre和cur指针。
最后，cur 指针已经指向了null，循环结束，链表也反转完毕了。 此时我们return pre指针就可以了，pre指针就指向了新的头结点。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode prev = null;
ListNode cur = head;
ListNode temp = null;
while (cur != null) {
temp = cur.next;// 保存下一个节点
cur.next = prev;
prev = cur;
cur = temp;
}
return prev;
}
}
4.2 递归
5. 两两交换链表中的节点 24. Swap Nodes in Pairs
虚拟头节点：
初始时，cur指向虚拟头结点，然后进行如下三步：
操作之后，链表如下：
Time: O(n)/Space: O(1)
注：
- node1 = node2，把node2的数据(val+next)给node1
- node1.next = node2，把node1指向node2，即node1的next中储存node2的地址
- node1.next.next = node2， 如果node1指向node3，即node3指向node2
class Solution {
public ListNode swapPairs(ListNode head) {
ListNode dummyNode = new ListNode(0);
dummyNode.next = head;
ListNode prev = dummyNode;
while (prev.next != null && prev.next.next != null) {
ListNode temp = head.next.next; // 缓存 next
prev.next = head.next; // 将 prev 的 next 改为 head 的 next
// System.out.println(prev.next.val);
head.next.next = head; // 将 head.next(prev.next) 的next，指向 head
head.next = temp; // 将head 的 next 接上缓存的temp
prev = head; // 步进1位
head = head.next; // 步进1位
System.out.println(prev.val);
}
return dummyNode.next;
}
}
6. 删除链表的倒数第N个节点 19. Remove Nth Node From End of List
双指针+虚拟头节点
双指针的经典应用，如果要删除倒数第n个节点，让fast移动n步，然后让fast和slow同时移动，直到fast指向链表末尾。删掉slow所指向的节点就可以了。
-
定义fast指针和slow指针，初始值为虚拟头结点
step1 -
fast首先走n + 1步 ，为什么是n+1呢，因为只有这样同时移动的时候slow才能指向删除节点的上一个节点（方便做删除操作）
step2 -
fast和slow同时移动，直到fast指向末尾
step3 - 删除slow指向的下一个节点
step4
注意: returndummy.next，因为head可能被删除
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode slow = dummy;
ListNode fast = dummy;
for (int i = 0; i <= n; i++){
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return dummy.next;//注意要返回dummy.next，因为head可能被删除
}
}
7. 链表相交 160. Intersection of Two Linked Lists
简单来说，就是求两个链表交点节点的指针。 这里同学们要注意，交点不是数值相等，而是指针相等。
-
看如下两个链表，目前curA指向链表A的头结点，curB指向链表B的头结点：
step1 -
我们求出两个链表的长度，并求出两个链表长度的差值，然后让curA移动到，和curB 末尾对齐的位置
step2 此时我们就可以比较curA和curB是否相同，如果不相同，同时向后移动curA和curB，如果遇到curA == curB，则找到交点。否则循环退出返回空指针。
Time : O(n+m)/Space: O(1)
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode curA = headA;
ListNode curB = headB;
int lenA = 0;
int lenB = 0;
while(curA != null){
lenA++;
curA = curA.next;
}
while(curB != null){
lenB++;
curB = curB.next;
}
curA = headA;
curB = headB;
if(lenB > lenA){
int temp = lenA;
lenA = lenB;
lenB = temp;
curA = headB;
curB = headA;
}
int dif = lenA - lenB;
for (int i = 0; i < dif; i++){
curA = curA.next;
}
while(curA != null ){
if(curA == curB){
return curA;
}
curA = curA.next;
curB = curB.next;
}
return null;
}
}
8. 环形链表
8.1 141. Linked List Cycle
HashSet
把链表中的节点都存进去，并判断是否已经存在，因为HashSet中元素不重复。
public class Solution {
public boolean hasCycle(ListNode head) {
HashSet<ListNode> set = new HashSet<ListNode>();
while(head != null){
if(set.contains(head)){
return true;
}
set.add(head);
head = head.next;
}
return false;
}
}
8.2 142. Linked List Cycle II
双指针
fast每次走两步，slow每次走一步，若有环，两指针必定相遇。
相遇后fast回到head，fast改为每次走一步，slow继续每次走一步，相遇点即是入环节点
public class Solution {
public ListNode detectCycle(ListNode head){
if(head == null || head.next == null || head.next.next == null){
return null;
}
ListNode slow = head.next;
ListNode fast = head.next.next;//两个点的初始条件不能相同，因为下面while的判断条件时相不相同
while (fast != slow){
if(fast.next == null || fast.next.next == null){
return null;
}
fast = fast.next.next;
slow = slow.next;
}
fast = head;
while(fast != slow){
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
