💎 欢迎各位大佬互三：我的主页

1. 反转链表

206.反转链表

思考：如果不开辟额外的空间，只在原来的链表上进行修改的话，该用什么方法呢

只需要从第二个元素开始，依次进行头插就可以了

接着修改一下引用就可以了，还要把末尾元素指向null

class Solution {    public ListNode reverseList(ListNode head) {        //head为null，直接返回        if(head == null){            return head;        }        ListNode cur = head.next;        //head变为了末尾元素，指向null        head.next = null;        while(cur!=null){            //curn为cur的next节点，便于往后移动            ListNode curn = cur.next;                cur.next = head;            head = cur;            //更新cur            cur = curn;        }        return head;    }}

2. 链表的中间节点

876. 链表的中间结点

这道题首先想到的方法肯定是定义一个cnt ，遍历一遍链表，接着求出中间的数，再遍历返回值，这种方法很简单，那如果要求只遍历一遍链表就找出中间节点呢

这里提供一个新的思路：利用快慢指针，都从head开始，fast指针每次移动两个节点，slow每次移动一个节点，这样是不是就达到了最终的目的

接着我们来实现一下：

class Solution {    public ListNode middleNode(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;        }        return slow;    }}

这样是不是效率就更高了

3. 返回倒数第k个节点

面试题 02.02. 返回倒数第 k 个节点

这道题首先想到的应该还是遍历一遍得到总的长度，接着再找倒数第k个节点，不过有了上一题的基础，就可以想到另一种方法：同样的，利用快慢指针，让fast先走 k-1 个节点，然后slow和fast同时走，当fast的next为null时，就表示fast走到了最后一个节点，此时的slow就是倒数第k个节点

这道题中指明了输入的k是合法的，就不用再额外的判断了，那如果k是不合法的怎么判断，并且要求，不能直接求链表的长度，所以slow就需要边走边判断

class Solution {    public int kthToLast(ListNode head, int k) {        if (head == null) {            return -1;        }        ListNode fast = head;        ListNode slow = head;        int cnt = 0;        while (cnt != k - 1) {            //判断k的合法性，虽然本题不用判断            fast = fast.next;            if(fast == null){                return;            }            cnt++;        }        //slow和fast同时移动        while (fast.next != null) {            fast = fast.next;            slow = slow.next;        }        return slow.val;    }}

4. 合并链表

21. 合并两个有序链表

思路：只需要再定义一个新的节点newH，然后一次比较headA和headB的val，为了最后能找到合并之后的链表的头结点，还要定义一个tmp = newH，之后谁小tmp.next就指向谁

class Solution {    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {        ListNode head = new ListNode();        ListNode tmp = head;            while(list1!=null&&list2!=null){            if(list1.val < list2.val){                tmp.next = list1;                list1 = list1.next;                tmp = tmp.next;            }else{                tmp.next = list2;                list2 = list2.next;                tmp = tmp.next;            }        }        //判断剩余的情况        if(list1!=null){            tmp.next = list1;        }else if(list2!=null){            tmp.next = list2;        }        return head.next;    }}

5. 链表分割

CM11 链表分割

这个是牛客上的一道面试题，题意就是对链表进行分割，x左边是比x小的，右边是比x大的，并且不能改变原来的顺序

思路：定义一个新的节点cur遍历原来的链表(防止原来的链表被改变)，把比x大的都放到一个链表，比x小的都放在领一个链表，最后把这两个链表相连

public class Partition {    public ListNode partition(ListNode pHead, int x) {        ListNode bs = null;        ListNode be = null;        ListNode as = null;        ListNode ae = null;        ListNode cur = pHead;        while (cur != null) {            if (cur.val < x) {                //处理刚开始为null的情况                if (bs == null) {                    bs = be = cur;                }else{                    be.next = cur;                    be = be.next;                }            }else{                if(as == null){                    as = ae = cur;                }else{                    ae.next = cur;                    ae = ae.next;                }            }            cur = cur.next;        }        //都是比x大的情况        if(bs == null){            return as;        }        be.next = as;        //最后都要置为null，不然可能会报错        if(as!=null){            ae.next = null;        }        return bs;    }}

需要注意的是，如果都比x大，也就是bs = null，此时就直接返回as，还有就是如果最后要把as.next置为null

6. OR36 链表的回文结构

OR36 链表的回文结构

是牛客的一道题，因为其中有时间复杂度和空间复杂度的要求，意味着不能额外开数组，不然空间复杂度过不去，正常遍历就是O(n)的复杂度

思路是这样的：首先找到链表的中间节点slow，然后把从中间到末尾这部分进行反转，head节点往后遍历，slow也往后遍历，进行比较，如果值不相同，就意味着不是回文结构

反转链表和找中间节点前面已经练习过

public class PalindromeList {    public boolean chkPalindrome(ListNode head) {        if (head == null) {            return true;        }        //找到中间节点        ListNode fast = head;        ListNode slow = head;        while (fast != null && fast.next != null) {            fast = fast.next.next;            slow = slow.next;        }        //从slow开始到末尾反转        ListNode cur = slow.next;        while (cur != null) {            ListNode curn = cur.next;            cur.next = slow;            slow = cur;            cur = curn;        }        //判断回文        while (head != slow) {            if (head.val != slow.val) {                return false;            }            //判断偶数节点            if (head.next == slow) {                return true;            }            head = head.next;            slow = slow.next;        }        return true;    }}

需要注意的是，奇数节点的链表和偶数节点的链表的判断也有区别

偶数节点移动到上面的这种情况就会死循环，所以对于偶数节点还要额外判断

7. 相交链表

160. 相交链表

相交链表也就是一个类似于“ Y ”的转化，如图所示

下面的题中的图也很清楚

思路：因为无论是A短还是B短，他们的差值都是相交前的一部分，只需要把长的链表移动一个差值，接着两个链表节点同时往后移动，他们相同的节点就是要相交的那个节点

public class Solution {    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {        ListNode pl = headA;        ListNode ps = headB;        int cnta = 0,cntb = 0;        //计算两个链表的长度        while(pl!=null){            pl = pl.next;            cnta++;        }        while(ps!=null){            ps = ps.next;            cntb++;        }        //如果链表b长，就更新pl,ps        int len = cnta - cntb;        //上面求长度时pl,ps都为空了，所以这里再重新指向        pl = headA;        ps = headB;        if(len < 0){            pl = headB;            ps = headA;            len = cntb - cnta;        }        //移动差值        while(len!=0){            pl = pl.next;            len--;        }        //找到相交节点        while(pl!=ps){            pl = pl.next;            ps = ps.next;        }        //链表不相交的情况        if(pl == null) return null;        return pl;    }}

最后还需要加上不相交的情况，虽然在本题中不加也能过，不过为了严谨性还是要加上

8. 环形链表

8.1 判断是否有环

141. 环形链表

怎么去判断一个链表是否有环：还是使用快慢指针，就像两个人在操场跑步，一个人跑的快，一个人跑的慢，由于操场是一个环形，所以跑的快的肯定可以超过跑的慢的一圈，这时他们就相遇，但如果不是环，他们永远也不能相遇，就像你怎么追都追不到的女神一样

但是还有一种情况，如果是两个节点的环，定义的fast指针一次走3步，slow指针一次走1步，那他们还是永远也相遇不了

所以定义的指针每次走几步也需要判断，如果一个走2步，一个走1步，肯定是能相遇的

public class Solution {    public boolean hasCycle(ListNode head) {        ListNode fast = head;        ListNode slow = head;        while(fast!=null&&fast.next!=null){            fast = fast.next.next;            slow = slow.next;            if(fast == slow) return true;        }        return false;    }}

8.2 返回入环口的节点

142. 环形链表 II

这次需要在上题中判断是否为环后找出进入环的入口点，可以进行以下推理

public class Solution {    public ListNode detectCycle(ListNode head) {        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;        slow = head;        //寻找环        while(slow!=fast){            slow = slow.next;            fast = fast.next;        }        return slow;    }}

需要补充的是：

当环很小的时候，最终的化简结果就变成了上面的，但原来的代码还是没问题的