一.LinkedList的方法

首先先看一下链表的方法：

二.反转链表

题目对应LeetCode：206. 反转链表

/**  * 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 reverseList(ListNode head) {         if(head==null || head.next==null){             return head;         }                  ListNode pr=head;         ListNode cur=head.next;         ListNode p=cur.next;          while(cur!=null){             cur.next=pr;              pr=cur;             cur=p;             if(p!=null){                 p=p.next;             }         }          head.next=null;          return pr;     } }

思路：从前往后将每一个节点的next改成其前一个节点。

定义三个ListNode变量指向三个节点，cur指向的是当前要改变next的节点，pr指向的是cur.next要指向的节点，p是记录的作用，如果cur的next变成指向前面了，那么本来cur后面一个节点就丢失了，无法完成反转。

三.快慢指针在链表的应用

不少题目的解题关键就在快慢指针。

首先是最经典的应用：LeetCode：876. 链表的中间结点

题目意思就是返回中间结点，最笨的办法就是将链表遍历一遍，看看有多少个结点，然后再遍历出中间结点。这里使用快慢指针可以一步到位。

/**  * 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 middleNode(ListNode head) {         if(head==null){             return head;         }          ListNode slow=head;         ListNode fast=head;          while(fast!=null && fast.next!=null){             slow=slow.next;             fast=fast.next.next;         }          return slow;     } }

定义一个快指针和一个慢指针，让快的一下走两步，慢的一下走一步，这样走到最后停止时，slow刚好在中间结点上。

这个可以说是一个元问题，很多链表的题目都有这道题快慢指针的影子。

像非常经典的回文链表问题：CR 027. 回文链表，用的都是快慢指针的思想。

四.相交链表

题目对应LeetCode：160. 相交链表

这是题目的描述：给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。

由例图可以看出，在两个单链表相遇之后，交点后面的结点都是相同的。先考虑最简单的情况，如果两个链表的长度相同，那么直接从头开始一个一个遍历，知道找到交点。但是这个方法在双方长度不一时用不了。既然用不了，那我们就借着这个思路改一下，给短的链表补上不就行了，换句话说，链表从后往前对齐，长链表前面多的那部分不可以有结点，直接跳过即可，这样问题就解决了。

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {         if(headA==null && headB==null){             return null;         }          int len=0;         int lb=0;         int la=0;          ListNode cur=headA;         while(cur!=null){             la++;             cur=cur.next;         }          cur=headB;         while(cur!=null){             lb++;             cur=cur.next;         }          ListNode l=headA;         ListNode s=headB;         len=la-lb;         if(la

/**  * Definition for singly-linked list.  * class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public boolean hasCycle(ListNode head) {         if (head == null) return false;         ListNode slow=head;         ListNode fast=head;          while(fast!=null && fast.next!=null){             slow=slow.next;             fast=fast.next.next;              if(slow==fast){                 return true;             }         }         return false;     } }

/**  * Definition for singly-linked list.  * class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) {  *         val = x;  *         next = null;  *     }  * }  */ public class Solution {     public ListNode detectCycle(ListNode head) {         ListNode slow=head;         ListNode fast=head;          while(true){              if(fast==null || fast.next==null){                 return null;             }                          slow=slow.next;             fast=fast.next.next;              if(fast==slow){                 break;             }         }           slow=head;          while(slow!=fast){             slow=slow.next;             fast=fast.next;         }          return slow;     } }