反转链表
思路解透
本题就是通过不停地将最先的 head 节点位置的后一位插到最前面，完成链表的反转
本题需要两个节点变量
cur：其任务就是定位到原head节点位置的前一位，然后将自己插入到当前head节点的前面
- 因为链表的最后一个节点都是指向一个
null值，所以需要将最先的head节点的next置为空 - 但在将
head.next置为null之前，需要先将cur节点实例化出来，不然cur就无法找到原先的head节点的位置了
curN：其任务就是定位到cur的后一个节点，方便让cur进行循环插入
- 其在循环中进行实例化，因为每一次插入完成之后，
curN的位置都是需要随着cur的改变而改变 curN实例化为cur的下一个节点。在cur插入完成后，cur就会定位到curN的位置，若此为止不为null，则继续进行前插
代码解析
class Solution { public ListNode reverseList(ListNode head) { //1. 防止空指针异常 if(head == null){ return head; } //2. 将head.next置为空 //注意先把 cur 节点给先弄出来 ListNode cur = head.next; head.next = null; //3. 进行循环头插 while (cur != null) { ListNode curN = cur.next; cur.next = head; head = cur; cur = curN; } return head; } }
寻找中间节点
思路解透
解法 1：定义一个 cur 节点，从 head 节点的地方，向后走 size()/2 步，就到了中间位置
解法 2：定义一个 slow 节点，一次走一步，在定义一个 fast 节点，一次走两步，当 fast 走完的时候，slow 就刚好在中间位置（快慢指针）
- 当有偶数个节点时，循环判断条件为：
fast != null - 当有奇数个节点时，循环判断条件为：
fast.next != null - 这里的两个条件判断顺序不能换，否则会报空指针异常错误
快慢指针原理：
路程一样的情况下，速度是两倍，那么当走完的时候，路程也是两倍
代码解析（法 1）
public ListNode middleNode(){ int count = 0; ListNode node = head; while(node != null){ count++; node = node.next; } ListNode cur = head; for (int i = 0; i < count/2; i++) { cur = cur.next; } return cur; }
代码解析（法 2）
public ListNode middleNode(){ ListNode slow = head; ListNode fast = head; while(fast != null && fast.next != null){ //slow走一步，fast走两步 slow = slow.next; fast = fast.next.next; } return slow; }
返回链表中倒数第 k 个节点
思路解透
- 首先判断 k 是否合法，链表是否为为 null
k <= 0，返回-1- （下面的第二点看完再回来）因为如果
k大于链表长度的话，当fast走k - 1步的时候就会走出链表，所以在fast走k-1步的过程中如果出现fast == null，则返回-1
- 定义两个节点，
fast先走k - 1步，随后fast和slow一起走，当fast走到最后了，slow所在的地方就是倒数第k个节点
代码解析
public int kthToLast(int k) { //判断k是否合法，链表是否为null if(k <= 0 || head == null) { return -1; } ListNode fast = head; ListNode slow = head; int count = 0; while (count != k - 1) { //fast先向后走k-1步 fast = fast.next; if(fast == null){ //判断k是否合法 return -1; } count++; } while (fast.next != null){ //两个节点一起向后走，直到fast走到最后一个 fast = fast.next; slow = slow.next; } return slow.val; }
合并两个有序链表
思路解透
创建一个新的链表，为虚拟节点（傀儡节点），然后对需要合并的两个链表中的值进行比较，谁小谁就接在虚拟节点后面
- 创建一个新的节点
newH，在这个链表上进行合并，再创建一个tmp节点，用来指向newH链表中的最后一个节点 - 当
headA != null && headB != null的时候，进行比较
- 若
headA. val < headB. val，则将headA这个节点接在newH后面，即接在tmp节点后面，最后tmp和headB节点均向后移一位 - 若
headA. val > headB. val，则将headB这个节点接在newH后面，即接在tmp节点后面，最后tmp和headB节点均向后移一位
- 当
headA == null || headB == null的时候，剩下的一个链表里面的节点直接接到newH后面就行了 - 最后返回
newH. next，因为newH是一个虚拟节点，不存在于要合并的链表中，它只是一个引子
代码解析
public ListNode mergeTwoLists(ListNode headA, ListNode headB) { ListNode newH = new ListNode(0); ListNode tmp = newH; while(headA != null && headB != null){ if(headA.val < headB.val){ //将headA接到newH上面，随后后移 tmp.next = headA; headA = headA.next; tmp = tmp.next; }else if{ //将headB接到newH上面，随后后移 tmp.next = headB; headB = headB.next; tmp = tmp.next; } } if(headA == null){ //headA空了，将headB直接接到newH后面 tmp.next = headB; } //headB空了，将headA直接接到newH后面 if (headB == null) { tmp.next = headA; } return newH.next; }
分割链表
思路解透
构建两个区间，一个里面接上小于 x 的节点，一个里面接上大于 x 的节点，最后将这两个区间连接起来
- 若链表为空
- 遍历链表
- 创建一个
cur节点，用来遍历链表
- 把对应的节点放到指定区间
- 在小区间里
- 创建
bs（before start） 节点指向区间里面最前面的一个节点，创建be（before end） 节点指向区间里面最后一个节点 - 在小区间里面插入第一个节点的时候，
bs和be都指向这个节点，随后cur向后移 - 之后插入的节点均为尾插，
bs位置不变，be始终指向新插入的节点
- 在大区间里
- 创建
as（after start） 节点指向区间里面最前面的一个节点，创建ae（after end） 节点指向区间里面最后一个节点 - 在小区间里面插入第一个节点的时候，
as和ae都指向这个节点，随后cur向后移 - 之后插入的节点均为尾插，
as位置不变，ae始终指向新插入的节点
- 把两个区间连接起来
- 将
be节点和as节点连接起来，并且将ae节点的next置为null，作为新链表的尾巴，并且返回bs节点 - 若所有节点全在小区间里，就将
be节点的next置为null，作为新链表的尾巴，并且返回bs节点 - 若全在大区间里，则返回
ae节点
代码解析
public ListNode partition(ListNode pHead, int x) { //判断空链表 if(pHead == null){ return null; } //小区间的两个节点 ListNode bs = null; ListNode be = null; //大区间的两个节点 ListNode as = null; ListNode ae = null; //遍历链表的节点 ListNode cur = pHead; while(cur != null){ //插入小区间 if(cur.val < x){ //第一次插入 if(bs == null){ bs = be = cur; }else{ be.next = cur; be = be.next; } //插入大区间 }else{ //第一次插入 if(as == null){ as = ae = cur; }else{ ae.next = cur; ae = ae.next; } } cur = cur.next; } //当节点全部都在小区间时，直接返回大区间 if(bs == null){ return as; } //进行大小区间的拼接 be.next = as; //大区间不为空，把最后一个节点置空，作为尾巴 if(as != null){ ae.next = null; } return bs; }
回文链表
链表的回文结构_牛客题霸_牛客网 (nowcoder.com)
思路解透
- 首先用快慢指针找到中间的节点（上面第二题有讲解）
- 再对后半部分进行反转（上面第一题有讲解）
- 最后让首尾两个节点往中间走，直到相遇，返回
true；若是偶数个节点，则只需要前面节点的next与后面节点的值相等即可返回true
代码解析
public boolean chkPalindrome(ListNode head) { // write code here if (head == null) { return true; } //1. 找到链表的中间节点 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; } //2. 反转后半节点 ListNode cur = slow.next; slow.next = null; while (cur != null) { ListNode curN = cur.next; cur.next = slow; slow = cur; cur = curN; } //3. slow从后往前，head从前往后，直到相遇 while (head != slow) { if (head.val != slow.val) { return false; } //当节点个数为偶数 if (head.next == slow) return true; head = head.next; slow = slow.next; } return true; }
相交链表
思路解透
- 首先计算两个链表的长度，并计算他们的差值
- 随后让长的链表的头节点先走“差值“步，让他们站在同一起跑线
- 最后让他们携手同行，直到相遇，返回任意一个链表；若最终零个引用都为空，证明不相交，返回
null
代码解析
public ListNode getIntersectionNode(ListNode headA, ListNode headB) { //1. 计算两个链表的长度，并计算差值 int lenA = 0; int lenB = 0; ListNode curA = headA; ListNode curB = headB; while (curA != null) { curA = curA.next; lenA++; } while (curB != null) { curB = curB.next; lenB++; } int len = lenA - lenB; curA = headA; curB = headB; //2. 根据差值，长的链表头节点先走len步， // 让两个链表在同一起跑线 if (len > 0) { int count = 0; while (count != len) { curA = curA.next; count++; } } else { int count = 0; while (count != -len) { curB = curB.next; count++; } } //3. 两个链表的节点携手同行，直到相等 while (curA != curB) { curA = curA.next; curB = curB.next; } if (curA == null) { //若两个引用都为空，证明不相交 return null; } return curA; }
环形链表
思路解透
- 定义两个节点，一个一次走一步，一个一次走两步
- 当走得快的节点不为空，并且走得快的节点的 next 不为空，循环就一直继续
- 当两个节点相等，则返回
true
假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况
因此：在慢指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。
代码解析
public boolean hasCycle(ListNode head) { ListNode fast = head; ListNode slow = head; while(fast != null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) return true; } return false; }
环形链表Ⅱ
思路解透
代码解析
public ListNode detectCycle(ListNode head) { //1. 判断是否有环 ListNode fast = head; ListNode slow = head; while (fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; //有环，跳出循环 if (fast == slow) { break; } } //若是因为没有环而跳出循环的话，返回null if (fast == null || fast.next == null) { return null; } //此时slow在相遇点，将fast拿到起始点 //让他们相向而行，相遇点即为入口点 fast = head; while(fast != slow) { fast = fast.next; slow = slow.next; } return fast; }
