目录

一、输出链表中间节点

二、链表倒数第K个节点

方法一

方法二

三、交叉链表寻找交点

四、带环链表找入口

方法一

方法二

五、复制带随机指针的链表

总结

---

一、输出链表中间节点

leetcode(876题)

方法：使用快慢针的方法，快的指针走2步，慢的指针走一步。当快的走到末尾的时候，慢的指针正好走到中间。由于方法比较简单，不再赘述。下面的方法和快慢针是一样的。

    public ListNode middleNode(ListNode head) {ListNode s=head;ListNode f=head;int n=0;while(f!=null){f=f.next;n++;if(n%2==0){s=s.next;}}return s;}

二、链表倒数第K个节点

题目链接

链表中倒数第k个结点_牛客题霸_牛客网

方法一

同样使用快慢针的方法，我们可以让快指针先走K步，然后慢指针和快指针一起走，当快指针走到null时，慢指针正好走到倒数第K个。

    public ListNode FindKthToTail(ListNode head, int k){ListNode fast=head;ListNode slow=head;for(int i=0;i<k;i++){if(fast==null){return null;}fast=fast.next;}while(fast!=null){slow=slow.next;fast=fast.next;}return slow;}

方法二

我们直接计算出要走多少步才能到到倒数第K个，然后直接返回就行了。

    public static int length(ListNode head){int length=0;ListNode c=head;while(c!=null){c=c.next;length++;}return length;}public ListNode FindKthToTail2(ListNode head, int k){int length=length(head);ListNode cur=head;if(length<k || k<0){return null;}for (int i = 0; i < length-k; i++) {cur=cur.next;}return cur;}

三、交叉链表寻找交点

leetcode(160题)

方法：利用快慢指针的方法，只让长的链表的节点先走两个链表相差的步数，然后再一起往后走，直到遇到节点数值相等的情况或者为空的情况，输出对应的结果即可。由于不知道哪个链表更长，所以我们需要分情况讨论。代码如下：

    public static int length(ListNode head){int length=0;ListNode c=head;while (c!=null){c=c.next;length++;}return length;}public ListNode getIntersectionNode(ListNode headA, ListNode headB){int lengthA=length(headA);int lengthB=length(headB);ListNode ca=headA;ListNode cb=headB;if(lengthA>lengthB){for (int i = 0; i < lengthA - lengthB; i++) {ca=ca.next;}while(ca!=null&&cb!=null){if(ca== cb){return ca;}ca=ca.next;cb=cb.next;}return null;}else{for (int i = 0; i < lengthB - lengthA; i++) {cb=cb.next;}while(ca!=null&&cb!=null){if(ca== cb){return ca;}ca=ca.next;cb=cb.next;}return null;}}

四、带环链表找入口

leetcode(142题)

方法一

        有个巧妙的方法可以检测，利用快慢指针，一个走2步，一个走1步，只要链表有环，快慢指针一定可以相遇。对于入口的寻找我们可以在相遇处间断这个环，将相遇处节点和原来的头节点看作链表的开头，这样就转化为交叉链表寻找交点了。

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {int la=length(headA);int lb=length(headB);ListNode pa=headA;ListNode pb=headB;if(la<lb){for (int i=0;i<lb-la;i++){pb=pb.next;}while(pa!=pb){pa=pa.next;pb=pb.next;}if(pa==null){return pa;}else{return pa;}}else{for (int i=0;i<la-lb;i++){pa=pa.next;}while(pa!=pb){pa=pa.next;pb=pb.next;}if(pa==null){return pa;}else{return pa;}}}public static int length(ListNode head){int length=0;ListNode c=head;while (c!=null){c=c.next;length++;}return length;}public ListNode detectCycle(ListNode head) {ListNode s=head;ListNode f=head;ListNode newhead=head;while(f!=null){f=f.next;if(f==null){return null;}f=f.next;if(f==null){return null;}s=s.next;if(s==f){newhead=s.next;s.next=null;break;}}return getIntersectionNode(head,newhead);}

方法二

        有个更加巧妙的方法可以找到环的入口。该方法请有兴趣的同学去证明，本文重点在于实现该方法。代码如下：

    public ListNode detectCycle_well(ListNode head){ListNode s=head;ListNode f=head;while(f!=null){f=f.next;if(f==null){return null;}f=f.next;if(f==null){return null;}s=s.next;if(s==f){break;}}ListNode c=head;while (c!=s){c=c.next;s=s.next;}return c;}

五、复制带随机指针的链表

leetcode(138题)

方法：由于带有随机的指针，我们不仅需要记录链表的节点位置，我们还需要记录随机的节点的位置。我们的思路分为3步：

1.遍历链表，将每个节点插入到对应的老节点的后面

2.记录random信息

3.将复制的链表剪出来

代码如下：

    public Node copyRandomList(Node head) {if(head==null){return null;}//1.遍历链表，将每个节点插入到对应的老节点的后面Node cur=head;while (cur!=null){Node newnode=new Node(cur.val);newnode.next=cur.next;cur.next=newnode;cur=newnode.next;}//2.记录random信息Node c=head;while (c!=null){Node n=c.next;Node cRandom=c.random;if(c.random==null){n.random=null;c=n.next;}else{n.random=cRandom.next;c=n.next;}}//3.将复制的链表剪出来Node h1=head;Node newhead=head.next;while (h1!=null){Node h2=h1.next;h1.next=h1.next.next;if(h2.next!=null){h2.next=h2.next.next;}
/*else{h2.next=null;   //此处可以不写，因为必定为null}
*/h1=h1.next;}//4.返回新链表的头节点return newhead;}

总结

        链表的题目一定要注意特殊情况的时候，有时候可以借助假头法、快慢针等方法。总之还需要多练习。