目录前置内容测试数据和print判断链表是否只有一个节点删除重复节点法一法二倒数第K个节点删除某节点链表分区链表加法有环链表的起点法一法二快慢指针判断回文链表法一反转链表法二法三法四法一法二前置内容链表的题经常用到两指针相遇快慢指针测试数据和printpublic class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val val; } ListNode(int val, ListNode next) { this.val val; this.next next; } }public static void main(String[] args) { // 创建链表 1 - 2 - 2 - 3 - 3 - 4 ListNode head new ListNode(1); head.next new ListNode(1); head.next.next new ListNode(3); head.next.next.next new ListNode(3); head.next.next.next.next new ListNode(5); head.next.next.next.next.next new ListNode(2); System.out.println(Before removing duplicates:); printList(head); test2(head); System.out.println(After removing duplicates:); printList(head); }public static void printList(ListNode head) { ListNode current head; while (current ! null) { System.out.print(current.val ); current current.next; } System.out.println(); }判断链表是否只有一个节点如果头结点的下一节点等于空则说明该链表只有一个节点删除重复节点题目移除未排序节点中的重复节点法一使用HashSet遍历链表使用HashSet存每个元素每次添加进HashSet之前先检查HashSet里面有没有有就删除没有就存上这样最后经过处理后的链表就去完重了。public static void test2(ListNode list1) { HashSetInteger con new HashSet(); ListNode t list1; con.add(t.val); while (t.next ! null) { if (con.contains(t.next.val)) { // 存在就删除 t.next t.next.next; } else { // 不存在就添加并移动指针 con.add(t.next.val); t t.next; } } }这里注意HashSet是根据对象引用存储地址判断是否相同。所以不能直接将整个节点都存入让HashSet自己去除重复的val。因为相同的val存储在不同的地址中也是不同的。对应看题“有环链表的起点”法二使用哨兵使用一个哨兵指向当前要检查的元素后遍历链表检查是否重复。而后哨兵移动重复上述步骤。简而言之就是双重for循环public static void test1(ListNode list1) { // 哨兵 ListNode temp list1; // 遍历指针 ListNode t list1; while (temp ! null) { while (t.next ! null) { if (temp.val t.next.val) { // 如果发现重复节点删除 t.next t.next t.next.next; } else { // 否则继续遍历下一个节点 t t.next; } } // 更新指针位置 temp temp.next; // 只查哨兵后面的节点有没有重复的即可 t temp; } }倒数第K个节点题目找出单向链表中倒数第K个节点法一使用双停指针推荐一个指针先走走到第k个节点后第二个指针指向头部这样两个指针之间的距离正好是k。此刻开始两个指针一起走当前面的指针指向末尾的时候后面的指针正好指向第k个节点。public static void test3(ListNode list1,int n) { // 快指针 ListNode fast list1; // 慢指针 ListNode slow list1; // 先将快指针移动到第n位 for (int i 1; i n; i) { fast fast.next; } // 而后快慢指针一起移动 // 快指针走到末尾结束 while (fast.next ! null) { fast fast.next; slow slow.next; } System.out.println(slow.val); }法二反转链表后删除第n个节点反转链表三个指针 pre curr next总的来说就是断后面连前面断掉后面之前先把节点用next保存一下防止丢失next curr.next;连前面的节点curr.next prev;移动指针pre和curr进行下一次的动作prev curr; curr next;完整代码public ListNode reverseList(ListNode head) { // 如果链表为空或只有一个节点直接返回头节点 if (head null || head.next null) { return head; } // 初始化三个指针 ListNode prev null; // 前一个节点 ListNode curr head; // 当前节点 ListNode next null; // 下一个节点 // 遍历链表逐个反转指针方向 while (curr ! null) { next curr.next; // 保存当前节点的下一个节点 curr.next prev; // 将当前节点的指针反转 prev curr; // 前一个节点后移 curr next; // 当前节点后移 } // 最终prev指向反转后的头节点 return prev; }法三先遍历链表数出链表的长度n再从头移动指针到第n-k个节点代码实现可以参考下面这道题删除倒数第n个节点在对链表进行操作时一种常用的技巧是添加一个哑节点dummy node它的 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 dummy new ListNode(0); dummy.next head; // 第一次遍历计算链表的长度 int length 0; ListNode temp head; while (temp ! null) { length; temp temp.next; } // 计算要删除节点的前一个节点的位置 int position length - n; temp dummy; // 移动到要删除节点的前一个节点 for (int i 0; i position; i) { temp temp.next; } // 删除指定节点 temp.next temp.next.next; // 返回新的头节点 return dummy.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) { if (head null) { return null; } if (head.next null) { // 只有一个节点直接删除 return null; } ListNode temp head; int count 1; while (temp.next ! null) { temp temp.next; count; } // 如果要删除头节点 if (count n) { return head.next; } // 挪到删除点的前一位 temp head; for (int i 1; i count - n; i) { temp temp.next; } // 如果要删除最后一位 if (n 1) { temp.next null; } else { temp.next temp.next.next; } return head; } }删除某节点这道题的特点就是我们只能得到一个需要删除的Node而没有整个链表也没有节点的前驱但我们能得到它的后继所以我们能删除后继。所以将该节点的后继的内容复制给需要删除的节点而后删除这个后继节点// 复制后继节点的内容 t.val t.next.val; // 删除后继节点 t.next t.next.next;链表分区遍历链表比基准值小的就连L-tail比基准值大的就连r-tail最后把两个链表连起来即可。链表加法两链表遍历相加即可public ListNode test4(ListNode l1, ListNode l2) { ListNode dummyHead new ListNode(0); ListNode p l1, q l2, current dummyHead; int carry 0; while (p ! null || q ! null) { int x (p ! null)? p.val : 0; int y (q ! null)? q.val : 0; int sum carry x y; // 将一个数除以 10 就能得到它的十位数字,也就是我们要的进位 carry sum / 10; current.next new ListNode(sum % 10); current current.next; if (p ! null) p p.next; if (q ! null) q q.next; } if (carry 0) { current.next new ListNode(carry); } return dummyHead.next; }有环链表的起点法一如果一直遍历第一个重复遍历的节点就是开头节点所以使用HashSet存每个节点这样当找到第一个存储地址相同的节点时return即可public ListNode test5(ListNode l1) { ListNode t l1; HashSetListNode con new HashSet(); // 这里由于是有环链表所以不会出现遍历到null的时候 // 所以是永远遍历不完的只有return能打断 // 所以while判断条件直接写ture即可 while (true) { if (con.contains(t)) { return t; } else { con.add(t); t t.next; } } }法二使用快慢指针不开辟新存储空间快慢指针用作解链表的题很多有两指针slow和fastslow指针一次走一步fast指针一次走两步。如果链表有环那么总会有某时刻两指针相遇指向同一点所以快慢指针可以判断链表是否有环右下角的黑字从“所以”那开始修改f通过兜圈的方式走够差的L-k步就能追上spublic static ListNode test6(ListNode l1) { ListNode fast l1; ListNode slow l1; // 两指针一直走,直到相遇 while (true) { fast fast.next.next; slow slow.next; if (fast slow) break; } // 相遇后头指针和slow一起走直到相遇 // 先处理特殊情况链表所有元素组成一个完整的环 // 这时候不应该移动指针头节点就是环的起点所以直接返回 if (slow l1) { return l1; } while (true) { l1 l1.next; slow slow.next; if (l1 slow) break; } return l1; }判断回文链表判断单链表是否是回文链表下面两个都是回文链表法一反转链表看是否和原串相等法二先把链表中的所有元素存到一个数组里然后利用双指针法从数组的两端向中间遍历比较对应位置的元素是否相等法三移动一个指针到末尾后新建指针指向开头两个指针对着走走一次比较一次。法四使用快慢指针利用slow指针走到kfast指针走到2k的特性当fast走到链表末尾的next时也就是null偶数链表slow 落在前半段最后一个节点奇数链表slow 落在中点// 找到链表的中点 ListNode slow head; ListNode fast head; while (fast.next ! null fast.next.next ! null) { slow slow.next; fast fast.next.next; }法一slow指针走的时候始终跟一个他的pre指针这样fast指向null时也就是s和f走到上图的位置时slow继续向前pre往回走每次移动都进行比较是否相同如果全部相同则是回文否则有一次不是就不是回文法二利用栈的先进后出特性slow指针从起点走的时候每次扫描的val都进栈fast指向null时slow继续向前走这时和出栈元素作比较全部相等则是回文否则有一次不是就不是回文法三后半段翻转与前半段比较