💐文章导读

本篇文章主要详细的用图解的方式为大家讲解了简单程度的链表题，如果题中有错误的地方，还麻烦您在评论区指出，你的意见就是我最大的进步！！！

💐专栏导读

🤴作者：🦁努力努力再努力

🏆文章专栏：🌷《JavaSE语法》 、 🌷《C语言初阶》、 🌷《图解LeetCode》、 🌺《数据结构剖析》

1、环形链表

思路：本体主要是利用双指针进行解题，分别定义一个快指针和慢指针，快指针一次走两步，慢指针一次走一步，如果链表有环的情况下，快慢指针直接差的距离最多是一个环的距离，肯定不会超过一个环，所以就需要用一个循环让快慢指针分别走，当两个指针相遇时，就返回true，就表明链表有环，如果循环结束了还没有返回，就表明链表没环，而循环结束的条件就是fast==null || fast.next == null时，表明链表已经走完了。

2.环形链表进阶版

    public ListNode detectCycle(ListNode head) {if(head == null) {return null;}ListNode fast = head;ListNode slow = head;while(fast!=null && fast.next!=null) {//查找在环中相遇时的节点fast = fast.next.next;slow = slow.next;if(fast == slow){break;}}if( fast==null || fast.next==null) {return null;}fast = head;while(fast != slow){fast = fast.next;slow = slow.next;}return fast;}

3.相交链表

思路：

如果要求两个链表的在什么地方相交，就要从两个链表的同一个节点向后遍历，所以首先要算出两个链表的长度差，让长的链表向后先走差值步，然后两个链表再一起向后走，直到遇见相同的地址处！

下面有图解：

public ListNode getIntersectionNode(ListNode headA, ListNode headB) {//1、分别求2个链表的长度int lenA = 0;int lenB = 0;int len = 0;ListNode curA = headA;ListNode curB = headB;while(curA != null) {lenA++;curA = curA.next;}while(curB != null) {lenB++;curB = curB.next;}curA = headA;curB = headB;len = lenA-lenB;if(len<0) {curA = headB;curB = headA;len = lenB-lenA;}for(int i=0; i<len; i++) {curA = curA.next;}while(curA!= null && curB!=null) {if(curA == curB){return curA;}curA = curA.next;curB = curB.next;} return null;}

4.删除排序链表中的重复元素

5.移除重复节点

双指针解法：
定义一个cur1指向头节点，再定义一个cur2指向cur1,用cur2区遍历所有的节点中val值与cur1中的val值作对比，如果相同就删除，否则就一直遍历

  public ListNode removeDuplicateNodes(ListNode head) {if(head == null) {return null;}ListNode cur1 = head;while(cur1 != null){ListNode cur2 = cur1;while(cur2.next != null){if(cur2.next.val == cur1.val) {cur2.next = cur2.next.next;}else{cur2 = cur2.next;}}cur1 = cur1.next;}return head;}

6.删除中间节点

解题思路：

要删除中间节点的话本来应该要找到中间节点的前驱的，但是现在只给了中间节点，那么可以这样做，可以把中间节点的后继节点中的val值赋给中间节点的val值，然后把后继节点删除掉，这样也符合题目要求

 public void deleteNode(ListNode node) {node.val = node.next.val;node.next = node.next.next;}

7.二进制链表转整数

   //第一种方法：利用按位或
public int getDecimalValue(ListNode head) {int ans = 0;ListNode cur = head;while(cur != null) {ans  = ans<<1;ans |= cur.val;cur = cur.next;}return ans;}
//第二种方法：利用换算二进制方法public int getDecimalValue(ListNode head){ListNode cur = head;int ans = 0;while(cur != null) {ans = ans*2+cur.val;cur = cur.next;}return ans;}

9.翻转链表

解题思路：

1、翻转链表就是将后面的每一个节点都存储前面一个节点的地址

2、因为链表都是从前向后走的，如果想要让后一个节点cur中的next变成前一个节点的地址，就需要知道前一个节点的地址；所以需要用一个变量prev来记录前一个结点，再用一个变量next来记录第三个结点，以方便中间的节点向后走，不然的话，当中间节点内的next改变以后，没办法找到第三个节点的位置，然后三个记录节点的变量分别向后走，这样知道前面一个节点和后面一个节点，就可以进行翻转！

   public ListNode reverseList(ListNode head) {if(head == null) {return null;}ListNode curprev = null;ListNode cur = head;while(cur != null) {ListNode next = cur.next;cur.next = curprev;curprev = cur;cur = next;}head = curprev;return head;}

10.链表中倒数第K个结点

解题思路：

1、求链表中倒数第K个结点，应该思考当给过k之后，应该怎么找这个倒数第k个节点，就拿题中给的事例来说，求倒数第二个结点就是4，可以用快慢指针的方法，而快慢指针的概念就是，假如有两个人A和B，它们都距离目的地差10步，如果让A先提前走三步，那么A和B之间就会差三步，然后让A和B在一人一步走，这样当A走到目的地时，B还是和A差三步远，而这个B正好在倒数第三个位置。路程不同，时间相同，速度相同，最后得到的就是路程差

所以此题定义一个fast快指针和slow慢指针，让快指针先走k步，当快指针走到空时，满指针正好在倒数第k的位置

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

11.从头到尾打印链表

解题方法：

1、先计算链表的长度，作为数组的长度

2、判断链表是否为空，为空则数组也为空，返回空数组

3、从数组的最后的下标开始放链表中的val

    public int[] reversePrint(ListNode head) {int len = 0;ListNode cur = head;//计算链表的长度while(cur!=null){len++;cur = cur.next;}int[] arr = new int[len];//如果链表为空则返回空数组if(head == null) {return arr;}因为数组下标是从0开始的所以减一int i =len-1;cur = head;while(cur!=null) {//从数组的最后开始放arr[i--] = cur.val;cur = cur.next;}return arr;}