找中点用快慢指针，快的一次性找俩，慢的找一个
ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ slow = slow.next; fast = fast.next.next; }遍历链表
ListNode cur = head; while(cur != null){ cur = cur.next; }插入节点
// 在 node 后插入 newNode ListNode newNode = new ListNode(5); newNode.next = node.next; node.next = newNode;反转链表
class Solution { public ListNode reverseList(ListNode head) { ListNode prev = null; ListNode cur = head; while(cur != null){ ListNode next = cur.next; // 保存下一节点 cur.next = prev; // 反转 prev = cur; // 前进 cur = next; } return prev; } }删除倒数第n个
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode fast = dummy; ListNode slow = dummy; // fast 先走 n 步 for(int i = 0; i < n; i++){ fast = fast.next; } // 一起走 while(fast.next != null){ fast = fast.next; slow = slow.next; } // 删除 slow.next = slow.next.next; return dummy.next; } }160-相交链表
给你两个单链表的头节点
headA和headB，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回null。题目数据 保证 整个链式结构中不存在环
思路：由于要找相同的部分，先右对齐两链表，然后一 一对比。右对齐需要找到两者差值，先把差值去掉，然后齐了再开始遍历。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //先判空 if(headA==null||headB==null){return null;} //先找到长度 int numA=0,numB=0; ListNode tempA=headA;ListNode tempB=headB; while(tempA!=null){numA++;tempA=tempA.next;} while(tempB!=null){numB++;tempB=tempB.next;} //跳过长度，对齐 if(numA>=numB){ for(int i=0;i<numA-numB;i++){ headA=headA.next; } } if(numA<numB){ for(int i=0;i<numB-numA;i++){ headB=headB.next; } } //开始遍历，相等结束 while(headA!=headB){ headA=headA.next; headB=headB.next; } return headA; } }细节注意：遍历链表取长度时，不能直接用原链表，会改变链表结构，选用新建temp来代替。
206-反转链表
思路：一个一个变，指向前面节点。但是要存好后一个，多多新建链表存不同的功能。新建翻转后的，新建平替操作的，新建下一个节点的。
/** * 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 ListNode reverseList(ListNode head) { ListNode pre=null; ListNode tem=head; while(tem!=null){ ListNode next=tem.next;//存下一个 tem.next=pre; //翻转链表 pre=tem; //pre更新 tem=next;//tem更新 } return pre; } }234-回文链表
给你一个单链表的头节点
head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。
思路：因为是回文单链表，先找中点，前一半翻转，然后对比两段是否相同（长度相等不需像160题一样对齐砍掉）。注意区分奇偶数
/** * 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) { ListNode fast=head; ListNode slow=head; ListNode per=null; //找中点翻转前一半 while(fast!=null&&fast.next!=null){ fast=fast.next.next; ListNode next=slow.next; slow.next=per; per=slow; slow=next; } //奇数跳过中点,奇数时fast还剩一个 if(fast!=null){ slow=slow.next; } //比较两端,翻转后存入per,比较per和slow while(per!=null&&slow!=null){ if(per.val!=slow.val){return false;} per=per.next; slow=slow.next; } return true; } }注意细节：
1、找中点的条件是 while (fast!=null &&fast.next != null )
2、比较两节点是否相等，用per.val 和slow.val
3、找中点奇数的话，最后多一个
141-环形链表
给你一个链表的头节点
head，判断链表中是否有环。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos不作为参数进行传递 。仅仅是为了标识链表的实际情况。如果链表中存在环，则返回
true。 否则，返回false。
思路：新建哈希集合存节点，看是否已存在。set . add(xxx)为true即集合未出现过，为false即出现过。
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { Set <ListNode> visited=new HashSet<ListNode>(); while(head!=null){ if(!visited.add(head)){ return true; } head=head.next; } return false; } }注意细节：1、新建集合 HashSet写法
2、set . add(xx)的逻辑
3、 if ( ! visited.add(head)) 会执行add，然后在判断是否存在
142-环形链表2
给定一个链表的头节点
head，返回链表开始入环的第一个节点。如果链表无环，则返回null。如果链表中有某个节点，可以通过连续跟踪
next指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数pos来表示链表尾连接到链表中的位置（索引从 0 开始）。如果pos是-1，则在该链表中没有环。注意：pos不作为参数进行传递，仅仅是为了标识链表的实际情况。不允许修改 链表。
思路：和上一题一样，因为要返回下标，使用把head替换到pos。返回pos即返回此时的下标，返回 pos.val 即返回此时的值。使用pos原因（使用后 head不变，后期返回要用到head，因为head遍历后变成了null）
/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { Set <ListNode> visited=new HashSet<ListNode>(); ListNode pos= head; while(pos!=null){ if(!visited.add(pos)){ return pos; } pos=pos.next; } return null; } }21-合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
思路：递归，一层一层两串进行比较并返回结果，从底层开始拼接结果。递归比正常while迭代的好处，不需要用新链表来接收，从底层开始自动拼接每一层返回结果。
判空则返回另一个有的，长度不一样时更适用。mergeTwoLists(a，b) 里面为去除开头的剩余部分。
/** * 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 ListNode mergeTwoLists(ListNode list1, ListNode list2) { if(list1==null){return list2;} else if(list2==null){return list1;} else if(list1.val<list2.val){ list1.next=mergeTwoLists(list1.next,list2); return list1; }else{ list2.next=mergeTwoLists(list1,list2.next); return list2; } } }2-两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
思路：两数相加，按照顺序依次，满10进1，加到下一组。将某数字a存入链表，必须先链表。next=new ListNode（a）才行。 最后一位如果有进位，则变成新节点。
/** * 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 ListNode addTwoNumbers(ListNode l1, ListNode l2) { int tem=0; ListNode list=new ListNode(); ListNode head=list; while(l1!=null||l2!=null){ int x=(l1!=null) ?l1.val:0; int y=(l2!=null) ?l2.val:0; int sum=x+y+tem; tem=sum/10; int det=sum%10; head.next=new ListNode(det); head=head.next; if(l1!=null){l1=l1.next;} if(l2!=null){l2=l2.next;} if (tem > 0) { // 如果最后还有进位 head.next = new ListNode(tem); // 加入一个新的节点保存进位 } } return list.next; } }注意细节：如果新建链表，必须用head来接一下，最后返回的话，用链表.next 如果直接链表则开头为空
19-删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第
n个结点，并且返回链表的头结点。
思路：快慢指针，快的先走n，慢的继续慢慢走。删除节点用a.next=a.next.next
/** * 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 ListNode removeNthFromEnd(ListNode head, int n) { ListNode list=new ListNode(); //新建返回链表 list.next=head;//与head对齐 ListNode fast=list; ListNode slow=list; 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 list.next; } }24-两两交换链表中的节点
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
思路：新建dummy存新链表，使用prev来搬运，每次判空后两个，交换后两个。prev始终更新到已完成链表的尾节点，然后更新prev。
class Solution { public ListNode swapPairs(ListNode head) { // 创建 dummy 节点，虚拟头结点 ListNode dummy = new ListNode(0); dummy.next = head; // prev 指向当前要交换的前一个节点，搬运工 ListNode prev = dummy; // 只要后面还有两个节点，就继续交换 while(prev.next != null && prev.next.next != null){ ListNode a = prev.next; // 第一个节点 ListNode b = prev.next.next; // 第二个节点 a.next = b.next;// 开始交换 b.next = a; prev.next = b;// prev 指向 b，接上已处理的链表 prev = a;//更新prev } // 返回新头节点 return dummy.next; } }138-随机链表的复制
给你一个长度为
n的链表，每个节点包含一个额外增加的随机指针random，该指针可以指向链表中的任何节点或空节点。构造这个链表的深拷贝。 深拷贝应该正好由
n个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的next指针和random指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。例如，如果原链表中有
X和Y两个节点，其中X.random --> Y。那么在复制链表中对应的两个节点x和y，同样有x.random --> y。返回复制链表的头节点。
用一个由
n个节点组成的链表来表示输入/输出中的链表。每个节点用一个[val, random_index]表示：
val：一个表示Node.val的整数。random_index：随机指针指向的节点索引（范围从0到n-1）；如果不指向任何节点，则为null。你的代码 只 接受原链表的头节点
head作为传入参数。
思路：每一个原节点后复制新节点，new一下。重新把随机指向关系放在新节点里。取出新头结点，拆分新节点。 每次头结点都需要重启。 注意判断条件是否null
/* // Definition for a Node. class Node { int val; Node next; Node random; public Node(int val) { this.val = val; this.next = null; this.random = null; } } */ class Solution { public Node copyRandomList(Node head) { if(head == null) return null; Node cur=head; //复制同样的一份在链表里 while(cur!=null){ Node newCur=new Node(cur.val); newCur.next=cur.next; cur.next=newCur; cur=newCur.next; } //重建链接关系 cur=head; //重启头结点 while(cur!=null){ if(cur.random!=null){ cur.next.random=cur.random.next; } cur=cur.next.next; } //拆分链表 Node newHead=head.next; Node newNode=newHead; cur=head;//重启头结点 while(cur!=null){ cur.next=cur.next.next;//恢复原节点 if(newNode.next!=null){ //只取新节点,新头为原头的下一位 newNode.next=newNode.next.next; } //新表剔除原节点 newNode=newNode.next; //新表走下一个 cur=cur.next;//走下一个 } return newHead; } }给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。
思路：排序且限制复杂度，链表选归并排序。使用递归持续截一半，最小单元比较大小，拼接往上返回。递归终止条件---快慢指针找中点切割---递归执行---调用排序函数add（）---add即按序合并两链表。
注意细节：递归判空条件必写。
找中点中归并排序的 fast起始值要多一个 因为目的是切割，不是找中间值。
切割设mid做右边链表的头结点。
结尾要把剩下的x或y存进去。
结果返回dummy.next dummy为虚拟头结点
/** * 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 ListNode sortList(ListNode head) { if(head==null||head.next==null){ //判空，递归的终止条件 return head; } //找中点 ListNode slow=head; ListNode fast=head.next;//起始多一个，利于切割，非找中间值 while(fast!=null&&fast.next!=null){ //fast去探路 slow=slow.next; fast=fast.next.next; } //切割 ListNode mid=slow.next;//做右边链表的表头 slow.next=null; //递归执行 ListNode left=sortList(head); ListNode right=sortList(mid); return add(left,right); } //拼接 public ListNode add(ListNode x,ListNode y){ ListNode dummy=new ListNode(); //存新结果 ListNode cur=dummy; //搬运工 while(x!=null&&y!=null){ if(x.val<y.val){cur.next=x; x=x.next;} //不能直接比，需要.val else{cur.next=y; y=y.next;} cur=cur.next; } if(x!=null){cur.next=x;} if(y!=null){cur.next=y;} return dummy.next; //dummy是头结点前一个 } }
