注：顺序是先筛选分类再按LeeCode上的通过率排的，每题最后的总结代码都是在LeeCode上跑过的，应该没啥问题。但是思路中的代码都是直接在CSDN编辑器里徒手敲的，若有笔误还烦请告知，蟹蟹~
22 链表中倒数第k个节点
兄弟们做链表题不画图的都是在耍流氓，与其空想花里胡哨的各种值应该怎么取，不如举个栗子，让所有取值跟着栗子走。
先说大体思路：这题就是快慢指针的板子，一个快指针先走k步，然后两指针再一起走，等快指针停了的时候慢指针就刚好是倒数k个位置了。
然后就是做链表最懵逼的取值问题了，我快指针是在while(!(quick == null))的时候停呢还是在while(!(queue.next == null))停呢？这时候不如把示例的例子拿出来自己走一遍，题目都把答案告诉你了，跟着这个思路肯定对。
花里胡哨的啥也不是，上代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode slow = head;
ListNode quick = head;
//快指针先走K步
for(int i = 0 ; i < k; i++){
quick = quick.next;
}
//快慢一起走，quick==null大胆写上去
while(!(quick == null)){
quick = quick.next;
slow = slow.next;
}
return slow;
}
}
24 反转链表
这题真是经典中的经典了，啥面经里都有它。
还是两个指针，再外加一个记录位置的指针，一路撸过去就完事了。
别急动笔先画图，画完之后再写代码：
上代码：
/**
* 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 before = null;
ListNode after = head;
while(!(after == null)){
ListNode tmp = after.next;
after.next = before;
before = after;
after = tmp;
}
return before;
}
}
35 复杂链表的复制
这题有点不太好描述，大致思路是在每个原节点的后面复制一个复制节点，然后再做一遍循环将每个复制节点的random指向对应的复制节点，最后再做一遍循环将复制节点与原节点分离。这个是链表深拷贝的思路，记住即可。
具体可以看这里
/*
// 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 pointer = head;
while(pointer != null){
Node tmp = new Node(pointer.val);
tmp.next = pointer.next;
pointer.next = tmp;
pointer = tmp.next;
}
pointer = head;
while(pointer != null){
if(pointer.random!=null){
pointer.next.random = pointer.random.next;
}
pointer = pointer.next.next;
}
Node res = head.next;
pointer = head;
Node copy = head.next;
while(pointer != null){
pointer.next = pointer.next.next;
pointer = pointer.next;
if(copy.next!=null){
copy.next = copy.next.next;
copy = copy.next;
}
}
return res;
}
}
52 两个链表的第一个公共节点
朝三暮四的故事了解一下：
有个玩猴子的人拿橡实喂猴子，他跟猴子说，早上给每个猴子三个橡子，晚上给四个，所有的猴子听了都急了；后来他又说，早上给四个，晚上给三个，所有的猴子就都高兴了（见于《庄子·齐物论》）。
怎么样让两个指针刚好相遇在第一个共同节点呢？道理和朝三暮四一样，你先走A走完再走B到第一个共同节点的距离，和先走B走完再走A到第一个共同节点的距离刚好是一样的。以题目中给的示例1为例：
秀呀，那万一没有共同节点怎么办呢？没有共同节点大家走到null的时候也是相等的，所以循环条件设置成while(A != B)就完事了。代码如下：
/**
* 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 A = headA;
ListNode B = headB;
while(A != B){
//A走完第一次，换到B的头继续走
if(A == null){
A = headB;
}else{
A = A.next;
}
//B走完第一次，换到A的头继续走
if(B == null){
B = headA;
}else{
B = B.next;
}
}
return A;
}
}
18 删除链表的节点
话不多说，链表不画图等于耍流氓：
普通的情况就很好理解，就指着删呗，但是万一删的是头结点咋办，你把头结点删了怎么去返回列表。所以这时候就在头结点前面再加一个节点res，指向头结点，反正怎么删都删不到我res头上，我的res.next就一定是返回值，舒坦。这就是传说中的虚拟头结点，牛逼哦！
这个想通了之后代码就照着图码就完事了，这题为啥通过率最低？蒙了。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode deleteNode(ListNode head, int val) {
ListNode res = new ListNode(0);
res.next = head;
ListNode pointer = res;
while(pointer.next.val != val){
pointer = pointer.next;
}
pointer.next = pointer.next.next;
return res.next;
}
}
到此为止链表的部分就结束啦~感觉剑指的链表题好少，估计等剑指刷完肯定要再刷刷LeeCode，就这几题感觉不太够呀。求个关注啵啵啵(●´З｀●)
顺便树的题目在这
转载：https://blog.csdn.net/qq_36329973/article/details/105433995