目录
0. 链表定义
/**
* 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; }
* }
*/
1. 移除链表元素
- 思路
1）首先设置一个新的链表头node，放入一个虚拟头结点
2）设置一个循环，快指针遍历链表使用快慢指针，如果快指针指向目标值，那么慢指针指向就跳过快指针这个点；如果不指向，那么快慢指针相等。
3）在判断完后，让快指针前进一位。
4）最后输出node的next，去掉头结点。 - 代码
class Solution {
public ListNode removeElements(ListNode head, int val) {
//链表的移除，设置虚拟头结点
ListNode node=new ListNode(-1,head); //在节点head前面添加一个节点-;
ListNode pre=node;
ListNode cur=node.next;
while(cur!=null){
if(cur.val==val){
pre.next=cur.next; //之后节点pre指向了cur.next，但是pre位置没变
}else{
pre=cur; //首先是连接，然后是pre就落在了cur上面
}
cur=cur.next;
}
return node.next;
}
}
- 注意事项
- 核心思路：链表节点的删除，使用快慢节点（pre和cur）
- 具体操作：首先定义一个头节点，使得对节点操作一致；然后就是遍历节点，跳过等于目标值的节点。
- 注意事项：1）一定要先设定头结点，能够一致操作；2）理解节点的跳跃关系：pre.next=cur.next操作，只是节点连接发生变化，pre的位置没变；pre=cur，节点位置发生变化了；综上：节点的等号，即为连接发生变化，位置没变；节点next的等号，即为节点位置发生变化。
2. 链表的设计
- 核心思路：链表的功能（包括定义一个节点类）
- 具体操作：核心功能就是链表的删除和添加。
3. 链表反转
- 代码
class Solution {
public ListNode reverseList(ListNode head) {
//核心思想：还是利用快慢节点
//1)定义三个节点
ListNode pre=null;
ListNode cur=head;
ListNode temp=null;
//2）利用中间节点，交换顺序（四个步骤的思路弄清楚）
while(cur!=null){
temp=cur.next; //保存下一个节点位置
cur.next=pre; //换方向
pre=cur; //结果对象
cur=temp; //回到原来的节点
}
//3）结果输出
return pre;
}
}
- 注意事项
- 核心思路：快慢节点，
- 具体操作：1）定义三个节点，pre,cur和temp临时节点；2）首先保存一下cur的下一个节点，然后把cur与节点pre连接起来得到新链表cur;3)新链表赋值给pre；4）之后再找回cur的下一个节点。
- 注意事项：1）首先把三个节点给设置好；2）之后就是把原链表一个一个节点剥离出来，反向连接到新的链表上面。
4. 两两交换链表中的节点
题目说明
思路：
1）首先设置头结点
2）交换三步曲
代码
class Solution {
public ListNode swapPairs(ListNode head) {
//1）定义虚拟节点
ListNode node=new ListNode(-1,head);
ListNode cur=node;
//2)进行循环，需要满足有两个情况下才进行循环
while(cur.next!=null && cur.next.next!=null){
//记录两个插入位置的临时节点，因为交换之后就会找不到原来的位置
ListNode temp1=cur.next;//节点1
ListNode temp2=cur.next.next.next;//节点3
//开始进行交换三部曲（等式左边带next即为连接的意思，右边为节点的意思）
cur.next=cur.next.next; //把虚拟头结点位置与节点2连接
cur.next.next=temp1; //把之后位置节点与节点1相连
cur.next.next.next=temp2; //把在后面一个位置与节点三相连
//更新cur的位置(向后移动两格)
cur=cur.next.next;
}
//3）输出(去掉头结点)
return node.next;
}
}
- 注意事项
核心思路：交换节点
具体操作：方法：1）设置虚拟头结点；2）以cur为基础，然后连接后面两个位置的原始；3）首先要保留交换之后不能用cur表示的节点；4）交换的三部曲；5）返回的节点要去除头结点
注意事项：1）始终是以cur为主节点进行连接；2）需要保存会丢失位置的节点1和节点3；3）交换三部曲，进行重新连接；4）返回的时候一定要去除头结点
5. 619. 删除链表的倒数第 N 个结点
- 题目
- 代码
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//核心思路：需要想办法提前感知到倒数第n个节点，然后进行交换；
//方法：通过设置一个相距n个节点两个节点：一个为目标的前一个对象，一个为最后一个对象
//1）添加虚拟头结点，使得一致性
ListNode node=new ListNode(-1,head);
//2)设置两个节点，距离为n个节点
ListNode pre=node;
ListNode cur=node;
for(int i=0;i<n;i++) cur=cur.next;
//3）两个节点起头并进，直到尾节点为空
while(cur.next!=null){pre=pre.next;cur=cur.next;}
//4)删除节点
pre.next=pre.next.next;
//5)输出
return node.next;
}
}
- 注意事项
- 核心思路：快慢节点指针
- 具体操作：方法：首先去找到删除节点的前一个节点，方法是设置两个相距n的节点，然后两个节点同时前进，如果后面一个节点的下一个节点为空了，则前面一个节点就是正确的位置。
- 注意事项：1）首先把三个节点给设置好；2）之后就是把原链表一个一个节点剥离出来，反向连接到新的链表上面。
6. 160.链表相交
题目说明
思路展示
1）a+c+b+c=b+c+a+c，把两个链表拼接起来，一定有一段是相同的代码说明
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//a+c+b+c=b+c+a+c:把两个链表相加起来，最后总有一个公共的c
ListNode head1=headA;
ListNode head2=headB;
while(head1!=head2){
head1=head1==null?headB:head1.next;
head2=head2==null?headA:head2.next;
}
return head1;
}
}
7. 141.环形链表
- 题目说明
- 代码
public class Solution {
public boolean hasCycle(ListNode head) {
//如何判断有环：设定快慢指针：快指针一下走两格，慢指针一下走一格
//如果是有环，那么一定是能够相遇的：因为如果有环存在，快指针会到慢指针后面
//之后就是没操作依次快一步了，能够赶上。
//1)一般情况
ListNode fast=head, slow=head;
while(fast!=null && fast.next!=null){ //易错点：因为下面出现了两个next,所以这里一定要先行判断
slow=slow.next;
fast=fast.next.next;
if(slow==fast)return true;
}
//2）输出
return false;
}
}
- 注意事项
- 核心思路：快慢指针
- 具体操作：1） while循环，使用快慢指针，如果两个指针相遇则退出；
- 注意事项：1）在大循环中，因为循环体中出现了fast=fast.next.next;fast!=null && fast.next!=null，这个在链表的题目里面非常关键。
8. 142.环形链表II
- 题目说明
- 思路说明
1）首先判断是否存在环：通过快慢指针，看看快慢指针是否会相遇（快指针一次走两步，慢指针一次走一步）初始位置都为头
2）在相遇的情况下，快指针位置不变，慢指针指向头结点，然后一步一步走，相遇的地方就是环入口。（涉及到一个数学的公式） - 代码说明
public class Solution {
public ListNode detectCycle(ListNode head) {
//判断是否存在环：设置一个快慢指针：
//快指针一次走两步，慢指针一次走一步
//如果存在环，快指针是一步一步趋向于慢指针的
ListNode fast=head;
ListNode slow=head;
while(fast!=null &&fast.next!=null){ //一定要对fast的后面两步进行判断，均非空才可
fast=fast.next.next; //两个循环都是先走再判断。
slow=slow.next;
if(slow==fast){
while(fast!=null){
ListNode temp=head;
temp=temp.next;
fast=fast.next;
if(fast==temp) return fast;
}
}
}
return null;
}
}
9. 25合并两个排序的链表
题目说明
代码
1）方法一：迭代法
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//方法一：使用迭代方法
ListNode result=new ListNode();
ListNode temp=result; //结果代理人
//1）当两边都不为空时
while(list1!=null &&list2!=null){
if(list1.val<=list2.val){
temp.next=list1;
list1=list1.next;
}else{
temp.next=list2;
list2=list2.next;
}
temp=temp.next;
}
//2）当一边为空时
if(list1==null) temp.next=list2;
if(list2==null) temp.next=list1;
return result.next;
}
}
2）方法二：递归法（思路需要掌握）
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
//递归方法
//截止条件
if(list1==null ) return list2;
if(list2==null) return list1;
//递归循环
if(list1.val<=list2.val){
list1.next=mergeTwoLists(list1.next,list2);
return list1;
}else{
list2.next=mergeTwoLists(list1, list2.next);
return list2;
}
}
}