update:
首先链表题，说到双指针那就应该是ListNode类型的,即不是考虑链链只需考虑节点。
然后就是一定会有head赋值发生。ListNode a =head之类的
还有就是节点判空是需要考虑的
一般需要while循环，while后面括号里是循环条件，一般是某位移节点不为空或某节点不等于某节点
红色是依然没有做出来的
141. 环形链表
public boolean hasCycle(ListNode head) { if(head==null||head.next==null) return false; ListNode ptA = head; ListNode ptB = head.next;//必须加，不然while进不去 while(ptA!=ptB){//while是满足执行，不满足才跳出 if(ptB==null||ptB.next==null) return false;//快的先到null就直接无环 ptA = ptA.next; ptB = ptB.next.next; } return true;//while不满足即a和b相等了则有环 } }
按照CS-Notes仓库的leetCode 题解来刷题
1. 找出两个链表的交点
160. Intersection of Two Linked Lists (Easy)
https://leetcode-cn.com/problems/intersection-of-two-linked-lists/description/
应该要知道一旦相交则后面的都是相同的。因为相交而拥有同一个Node，该Node只会指向唯一后继结点，则又是同一个Node。不会出现又分开的情况!!!
notes上分析和解法说的都很详细，就是a+c+b=b+c+a双指针法
即A先走自己的，走完了去走B的，B也先走自己的，走完了去走A的，这个过程中相遇的点就是交点。
/** * 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) { ListNode ptA=headA;//因为后面headA还有用所以不能破坏了 让替身去干 ListNode ptB=headB; while(ptA!=ptB){ //有相交点则在交点出退出循环 这里是因为pt是更新的值来做判断，不一定是A和B的next ptA= ptA==null?headB:ptA.next;//后面是一个三目判断 注意是ptA.next进行迭代 因为headA还有用不能被破坏所以找一个ptA=headA来赋值 ptB= ptB==null?headA:ptB.next; } return ptA; } }
详细分析：https://www.cnblogs.com/Yunus-ustb/p/12896382.html
notes上也分析地很详细了。
-----------------------------------------------------------入门有点困难，学习一下数据结构再来刷-------------------------------
2. 链表反转（头插法插入的顺序是反着的，s.next=l.next意思是s指向l的下一个）
206. Reverse Linked List (Easy)
https://leetcode-cn.com/problems/reverse-linked-list/
反转输出即在head前面插入值，但不是插进原链表
要新建一个链表输出，然后是原链表从第一个头head插进新链表，后面的也是依次头插进head前面。则5就在新链表的头结点的下一个上了。。。。
原链表插，则是原链表.next开头！！
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode dummy = new ListNode(-1);//哑结点 最后输出的链表 while(head!=null){ ListNode next = head.next;//让head.next用next暂存 head.next = dummy.next;// dummy.next = head;//这两步是头插法，在dummy与dummy.next之间插入了head节点 随后第二步是在dummy与dummy指向的head中间插head.next
由此实现反转 搞不明白去研究头插法就明白了
head = next;//而head现在是head.next了 } return dummy.next; } }
搞明白是谁头插谁啊输出的是什么很重要。。。
链表的头插法：
s.next=l.next;//这是s指向l的下一个！！！我想成了s的下一个指向l的下一个emmmmm
l.next=s;//这是l指向s！！！不是l的下一个指向s！！！！
node->next = head->next; // 将头指针所指向的下一个结点的地址，赋给新创建结点的next
head->next = node; // 将新创建的结点的地址赋给头指针的下一个结点
- 头插法插入的数据与插入的顺序相反；(插入两个，第二个插的在第一个前面，所以实现了反转）
- 尾插法插入的数据与插入顺序相同
链表的尾插法：
end.next=node;//end指向新的node
end=node;//node成为end
（对于链表的题目，首先可以考虑一下是不是需要用到 dummy 哑节点，用了哑节点之后题目会不会好做一点。 或者，考虑一下 curr工作指针。这都是思路的来源。
其次，链表的题目跟树的题目一样，都有一个指向另一个节点的指针。所以我们想一想题目是不是可以通过递归去做。这样避免了使用迭代的方式，减少自己的思考难度。）
递归的代码看着少其实很难写出来顺序。。
3. 归并两个有序的链表
21. Merge Two Sorted Lists (Easy)
https://leetcode-cn.com/problems/merge-two-sorted-lists/submissions/
class Solution { public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) return l2; if (l2 == null) return l1; ListNode dummy = new ListNode(-1); ListNode cur = dummy;//工作指针必须用了，如果还用dummy是无法输出多个值的 while(l1!=null&l2!=null){//循环条件看输入 if(l1.val<l2.val){ cur.next=l1; l1=l1.next; }else{ cur.next=l2; l2=l2.next; } cur=cur.next;//这里卡住了。。。没想到应该要用一个dummy的工作指针 } cur.next= l1==null?l2:l1; return dummy.next; } }
搞清dummy和cur，像206就可以只用dummy因为是头插，但该题需要指针遍历后赋值。
其实搞不太清。。。我好晕。。所以就都用cur去工作吧！！！把206也加入了cur...（0924清楚了）
4. 从有序链表中删除重复节点
83. Remove Duplicates from Sorted List (Easy)
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.
这题用不着哑结点啊直接在输入链表上操作就行啊...删除当前链表上的重复点。。。
把head赋值给cur。。。
class Solution { public ListNode deleteDuplicates(ListNode head) { if(head == null)return null; ListNode cur = head; while(cur!=null && cur.next != null){//指针代替head做判断了 if(cur.val==cur.next.val){ cur.next = cur.next.next; }else{ cur=cur.next;//0924这里卡。。。 } //不用管cur=cur.next了前面已经更新过了 } return head; } }
找出固定关系，递推就是。。
我感觉我脑子在冒烟了。。。我一开始用dummy和cur，那样cri=cur.next更新只能移一位，解决不了三个相等值。原来是得判断cur位移cur才行。
感觉明天就会忘记可怎么办。。。
还有notes上一直用的递归虽然能看懂但我写不出来。。但是真的要学会递归啊！（回头秋招也得学！）
5. 删除链表的倒数第 n 个节点
19. Remove Nth Node From End of List (Medium)
Given linked list: 1->2->3->4->5, and n = 2.
After removing the second node from the end, the linked list becomes 1->2->3->5.
好晕 这里又是用dummy.next=head 而不是cur。。吐血。。。(可以不用0924）
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(-1); ListNode cur = dummy; //dummy.next=head;//用的链表 dummy指向head？
cur.next=head;//也可以
ListNode p = head; int length = 0; int removeLength = 0; while(p!=null){ length++; p=p.next; }//得到head链表的长度！！！！ removeLength=length-n; while (removeLength > 0) { removeLength--; cur = cur.next; }//第一阶段得到前面相同的结点们 cur.next = cur.next.next;//删除点改指向 return dummy.next;//这就是dummy.next=head的好处 后面就不用管了都（这里想破头） } }
我怎么看完答案理解了思路也写不出正确的代码
coding能力太弱了。。。
0924三要素:
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
cur.next = head;
6. 交换链表中的相邻结点(设一个start节点一个end节点）
24. Swap Nodes in Pairs (Medium)
Given 1->2->3->4, you should return the list as 2->1->4->3.
题目要求：不能修改结点的 val 值，O(1) 空间复杂度。
class Solution { public ListNode swapPairs(ListNode head) { ListNode dummy= new ListNode(0); ListNode cur= dummy;
cur.next=head; while(cur.next != null && cur.next.next != null) {//得让指针来循环 即head和head.next // 这里的两个新建节点 start和 end有助于理解 ListNode start = cur.next; ListNode end = cur.next.next;
// 让 cur指向两个节点中的后一个（ end反转之后就是第一个） cur.next = end; // 进行反转 start.next = end.next; end.next = start;//这两步不能反 cur.next=end放这俩前面后面都可以
// 此时，第一个 start反转之后就变成最后一个，此时让cur等于它 cur= start; } return dummy.next; } }
搞清楚固定关系，才能从容应对循环，同题4,while出来后直接return。（用head换前三个没用的，要弄出关系好循环。。。
以后也首先考虑指针cur代替head循环。。
虽然没一题会的但往下走吧。。。。
7. 链表求和（用两个stack实现每个位上的值相加，且设置一个进位数）
445. Add Two Numbers II (Medium)
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
题目要求：不能修改原始链表。
class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { Stack<Integer> s1 = new Stack<>();//栈是这样定义的 Stack<Integer> s2 = new Stack<>(); while(l1 != null) { s1.push(l1.val); l1 = l1.next; }//实现把链表全部放入栈中 while(l2 != null) { s2.push(l2.val); l2 = l2.next; } ListNode dummy = new ListNode(-1); int carry = 0; while (!s1.isEmpty() || !s2.isEmpty() || carry != 0) {//要满足两栈都空且进位为0才能退出循环 int x = s1.isEmpty() ? 0 : s1.pop(); int y = s2.isEmpty() ? 0 : s2.pop(); int sum = x + y + carry; ListNode node = new ListNode(sum % 10);//余数写在该位结点上!!!!! node.next = dummy.next;//每一位余数来头插（插在dummy和它的next中间），后一位余数就插在在前一位前面 dummy.next = node; carry = sum / 10;//进位给下两个xy加上 } return dummy.next; } }
给我整麻木了已经。。。
0924：这题不要cur也行，要一个也行，之前是习惯性不要，现在习惯性要一个了。头插法啊又是！！因为是从后面算起，反着插入的！！！
8. 回文链表
234. Palindrome Linked List (Easy)
题目要求：以 O(1) 的空间复杂度来求解。
切成两半，把后半段反转，然后比较两半是否相等。
难以置信我居然还没搞懂i++和++i （若是只涉及i的更新，则两个都是自增；但若涉及式子的值，则需要注意了，i++第一下还是等于原来i的值的）
1.a = i++; 等校为
a = i;(a=1)
i = i + 1；
2.a = ++i; 等校为
i = i + 1；
a = i;(a=2)
class Solution { public boolean isPalindrome(ListNode head) { if (head == null || head.next == null) { return true; } ArrayList<Integer> list = new ArrayList<>(); ListNode p = head; while(p!=null){ list.add(p.val); p = p.next; } int start = 0;//头指针 int end = list.size()-1;//尾指针 求链表的长度不行。 while (start <= end) { if (!list.get(start).equals(list.get(end))) {//好像while里面的if总是写非正常条件 return false; }else{ start++;//只看i自增没用式子的值 所以++在前在后都可 都会自增 end--; } }//循环结束 return true; } }
9. 分隔链表
725. Split Linked List in Parts(Medium)
Input: root = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 3 Output: [[1, 2, 3, 4], [5, 6, 7], [8, 9, 10]]
class Solution { public ListNode[] splitListToParts(ListNode root, int k) { ListNode p = root; ListNode[] res = new ListNode[k]; int length = 0; while(p!=null){ length++; p=p.next; } ListNode cur = root; if(k>=length){ //错了res = root; //错了return res; //应该是把结点们一个一个按索引存入 for (int i = 0; i < length; i++) {//用length不能用k!!!! res[i] = new ListNode(cur.val);//8个索引 cur = cur.next; } } else{//必须分情况 int a = length%k;//8%3=2 则前a段要加1 int b = length/k;//8/3=2 每段基数是多少 btw除以会从少取整 //不会了。。。 cur = root;//索引0处 for (int i = 0; cur != null && i < k; i++) {//k=3 res[i] = cur;//0 1 2这三组3个索引 int curSize = b + (a-- > 0 ? 1 : 0);//3,3,2共8 这里a--是取值！！分隔且前面大就必须做这个判断！！！ for (int j = 0; j < curSize - 1; j++) { cur = cur.next;//指针后移 循环最后移停到索引2处 索引5处 索引7处 } ListNode next = cur.next;//先给他存起来下一段的开始点 cur.next = null;//截断这一段的结束点 cur = next;//后移为新的开始 索引3处 索引6处 } }return res; } }
好难写出。。。。
3个要点：1.分k大于等于length和小于length两种情况
2.小于时分k段 还得考虑每段基数是多少 前多少段要加1
3.小于时如何产生每一段 通过截断和开始
0924我下意识反应用queue...但是看答案queue好像更复杂了没人用这个解题
Queue<Integer> queue = new LinkedList<Integer>();
queue 为啥是new LickedList?
10. 链表元素按奇偶聚集
328. Odd Even Linked List (Medium)
Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.
拿到题目之后，第一时间想到的是把链表分成两条：一条奇数，一条偶数，这应该算是最朴素的想法了然后把它们连起来
(没想到。。。我想成第6题那样找关系了。。。）
第一步：头节点肯定是奇数节点，这毋庸置疑。所以odd = head，把头节点拿出来当奇数链表的头节点 第二步：头节点的下一个节点肯定是偶数节点了，所以even = head.next，把 head.next拿出来当偶数链表的头节点，
这里要注意了，一定要把偶数链表的头节点单独拿出来，这里我后面详细说
第三步：找出关系式，奇数链表的下下个节点才会是奇数节点，同样偶数节点的下下个节点才会是偶数节点 odd.next = odd.next.next even.next = even.next.next PS:之前做链表题目的时候，.next我经常搞混，但做得多了，我总结了一条经验 ‘=’左边的.next一般指的是该节点中存的next（链表节点包括两个部分组成，一个是val，一个是next用于指向下一个部分的），
而右边的.next一般来讲是指的指向的某个具体节点（0924终于在头插法那儿记住了这个）
第四步：找循环终止的条件，什么时候我们可以把所有的节点全部取完？ 当odd.next == None or even.next == None时，代表奇数或者偶数已经全部取完了，剩下的一个会根据它是奇数还是偶数填充到对应链表中 所以循环条件为 while odd.next and even.next: odd和even链表的头节点进一位（扮演迭代器,这里需要看图才理解。。。我想成到even上了，其实不会，因为第三步已经跳过了！！！ odd,even = odd.next,even.next
第五步：我第二步说的，为什么要把头节点拿出来，因为奇数链表的尾节点要跟偶数链表的头节点相连，从而形成完整的链表 odd.next = even_head 作者：zbzzbz 链接：https://leetcode-cn.com/problems/odd-even-linked-list/solution/zui-po-su-de-xiang-fa-dai-ma-zhu-shi-fei-chang-xia/
最终return的是head!!!!!!看图就很容易明白。看代码半天不明白为啥head啥也没做就返回head....看图就知道，由于odd和even已经让head后面已经全变化了。可见链表之间的赋值是真的把自己送给它了，然后他就能修改链表了。
我居然做了三天的题才反应过来这一点。。。（0924一天反应过来了。。。之前dummy和cur就是这样的关系）
class Solution { public ListNode oddEvenList(ListNode head) { if(head==null)return null; ListNode odd = head;//奇数链表头节点 ListNode even = head.next; ListNode evenHead = even;//拿出来之后做连接用 存起来 while(odd.next!=null&&even.next!=null){ odd.next=odd.next.next; even.next=even.next.next; odd=odd.next; even=even.next; } odd.next=evenHead; return head; } }
0924：看看代码其实这题还挺简单的，可是我看到说在原链表上原地完成就没有了思路。
应该想到定义odd节点与even节点的