1.快慢指针
先看一道简单的题目：返回中间结点
这道题有一个最朴素的做法就是先遍历一边链表，设置计数器求出链表长度，再重新走1/2的链表长度，即可返回中间节点
// 第二种解法 //这种解法需要遍历两次链表 ListNode cur1 = head; int cnt = 0; while(cur1 != null) { cnt++; cur1 = cur1.next; } ListNode cur2 = head; cnt = cnt/2; while(cnt != 0) { cur2 = cur2.next; cnt--; } return cur2;
但是这种方式有个明显的缺陷，就是你实际上是遍历了两遍链表，那有没有只遍历一次链表就能获得中间结点的方法呢？答案是有的，利用快慢指针
// 第一种解法 只需遍历一次链表 ListNode slow = head,fast = head; while(fast != null && fast.next != null) { fast = fast.next.next; slow = slow.next; } return slow;
快慢指针的核心思想其实是一种数学问题，即在相同时间内，路程之比就是速度之比
「力扣」第 19 题： 倒数第 k 个结点
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { // 使用虚拟头节点 -- 能更好的处理删除头节点的问题 ListNode dummyhead = new ListNode(0); dummyhead.next = head; ListNode slow = dummyhead; ListNode fast = dummyhead; while(n > 0) { fast = fast.next; n--; } while(fast.next != null) { fast = fast.next; slow = slow.next; } slow.next = slow.next.next; return dummyhead.next; } }
一个小细节：如果不使用虚拟头节点 在删除头节点的过程中会出错
数据结构--链表刷题(一)快慢指针（下）/article/1480782?spm=a2c6h.13148508.setting.15.361f4f0eyTL4lb
