链表的中间结点核心思想是利用快慢指针一个每次走一格一个每次走两格二者的差距就是整个链表长度的一半classSolution{publicListNodemiddleNode(ListNodehead){ListNodeslowhead,fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;}returnslow;}}注意题目中要求有偶数个结点的时候是返回的第二个结点如果是要返回第一个结点怎么办呢classSolution{publicListNodemiddleNode(ListNodehead){// 链表至少一个结点所以 head.next 不会报空指针异常ListNodefast,slow;slowhead;fasthead.next;// 先走一步while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}returnslow;}}让fast先多走一步相当于slow慢了一步这样slow作为中间节点就变成前面的了。反转链表两种方式一种遍历一种递归遍历的比较好理解遍历相当于是头插法把节点一点点放入另一个比如链表 1→2→3第一轮结束后得到链表 1第二轮结束后得到链表 2→1第三轮结束后得到链表 3→2→1classSolution{publicListNodereverseList(ListNodehead){ListNodecurhead;ListNodeprenull;while(cur!null){ListNodenxtcur.next;cur.nextpre;precur;curnxt;}returnpre;}}然后还可以递归reverseList(head)含义就是从head往下的链表已经反转完成了。相当于是尾插法迭代就是从前往后反转递归是从后往前反转比如 1→2→3→4→5我们反转一半 1→2→3←4←5我们要处理的是已经翻转完的和前面的怎么处理classSolution{publicListNodereverseList(ListNodehead){// head null 的判断是为了兼容一开始链表是空的情况// 实际上只需要 head.next null这是最后一个节点不需要反转作为头节点if(headnull||head.nextnull)returnhead;// 需要把头节点拿到实际上一直都是尾节点ListNodenewHeadreverseList(head.next);// 反转后续节点// 另 head.next 节点指向 headhead.next.nexthead;// 反转成功后head 节点不需要指向任何元素了head.nextnull;returnnewHead;}}当反转到某个中间状态时比如 1→2→3←4←5此时 3 节点的next是可以为空的不需要指向任何节点同时也不需要这个信息了只需向前继续处理让 2←3回文链表想实现O(1)空间复杂度只能改变链表本身的内容找到中间节点反转中间节点后续节点双指针一个从前一个从最后判断值是否相等来判断回文classSolution{publicbooleanisPalindrome(ListNodehead){ListNodemidgetMiddleNode(head);ListNodeendreverse(mid);while(head!nullend!null){if(head.val!end.val)returnfalse;headhead.next;endend.next;}returntrue;}privateListNodegetMiddleNode(ListNodehead){ListNodefast,slow;slowhead;fasthead.next;while(fast!nullfast.next!null){slowslow.next;fastfast.next.next;}returnslow;}privateListNodereverse(ListNodecurr){if(currnull||curr.nextnull)returncurr;ListNodenewHeadreverse(curr.next);curr.next.nextcurr;curr.nextnull;returnnewHead;}}如果我们设计函数可能本身没有这个意图的哈可能我只是需要你判断但是你改动了我的链表。我们可以这么做把数据拷贝到数组里面然后用数组双指针判断是否回文。classSolution{publicbooleanisPalindrome(ListNodehead){ListIntegervalsnewArrayList();ListNodecurrhead;while(curr!null){vals.add(curr.val);currcurr.next;}intfront0,backvals.size()-1;while(frontback){if(!vals.get(front).equals(vals.get(back)))returnfalse;front;back--;}returntrue;}}环形链表这个比较简单快慢指针如果有环的话快慢指针都会进入环并且永远出不去快指针肯定先进去慢指针后进去因为有环快慢指针的距离会慢慢减一所以一定会在环中相遇如果没有环快指针或者快指针下一个节点会为null直接返回false。publicclassSolution{publicbooleanhasCycle(ListNodehead){ListNodeslowhead,fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast){returntrue;}}returnfalse;}}环形链表II前面是判断是否为环形链表这里是找入口点前面只要判断出快慢指针在任意位置相遇即可但是相遇位置不一定在入口点但是我们需要先判断是否为环形链表再去找入口点有没有什么规律呢公式推导先定义三个距离ahead到环入口点的距离b环入口点到相遇点的距离c相遇点到环入口点的距离。因此环长为b c。慢指针到相遇点走了a b快指针的速度是慢指针的两倍并且比慢指针多走了完整的n圈至少一圈因此2 ( a b ) − ( a b ) n ( b c ) 2(ab)-(ab)n(bc)2(ab)−(ab)n(bc)化简可得a b n(b c)所以a ( n − 1 ) ( b c ) c \boxed{a(n-1)(bc)c}a(n−1)(bc)c这说明从head出发走a步刚好到达环入口从相遇点出发走a步相当于先走c步到达入口再绕(n-1)圈最终仍停在入口。因此让一个指针从head出发另一个指针从相遇点出发两者每次都走一步最终一定会在环入口相遇。while(head!slow){headhead.next;slowslow.next;}所以完整代码是publicclassSolution{publicListNodedetectCycle(ListNodehead){ListNodeslowhead,fasthead;while(fast!nullfast.next!null){fastfast.next.next;slowslow.next;if(slowfast){while(head!slow){headhead.next;slowslow.next;}returnslow;}}returnnull;}}合并两个有序链表这个就是两个指针分别遍历两个链表谁值小就加入新链表classSolution{publicListNodemergeTwoLists(ListNodelist1,ListNodelist2){ListNodeheadnewListNode();// 虚拟头节点ListNodecurrhead;while(list1!nulllist2!null){if(list1.vallist2.val){curr.nextlist1;list1list1.next;}else{curr.nextlist2;list2list2.next;}currcurr.next;}if(list1!null)curr.nextlist1;if(list2!null)curr.nextlist2;returnhead.next;}}这里你注意我们是真正的合并两个链表不是新建了第三个链表。