单链表的反转

头插法

两个指针，next 表示 head 的后一个节点，pre 表示 head 的前一个节点，都作为临时节点先把 head 节点指向后面节点的指针保存起来 next = head.next ，则此时 next 节点和 2 节点值和指针是相同的head 指向前一个节点 head.next = prepre 与 head 进行右移 pre = head，head = next

public static ListNode ReverseList(ListNode head) {    ListNode pre = null;    ListNode next = null;    if (head == null || head.next == null){        return head;    }    while (head != null){        next = head.next;        head.next = pre;        pre = head;        head = next;    }    return pre;}递归*斜体文字*public static ListNode ReverseListStack(ListNode head){    if (head == null || head.next == null){        return head;    }    ListNode node = ReverseListStack(head.next);    head.next.next = head;    head.next = null;    return node;}

链表的倒数第 K 个节点

1.双指针解决

2.fast 先走K步，然后 low 开始走，fast 走到结尾的时候 low 则指向倒数第 K 个节点3.主要 异常情况，K < 0 ，K > len(List)

public static ListNode getKNode(ListNode head,int k){    if (head == null || k < 0){        return null;    }    ListNode pre = head;    ListNode next = head;    for (int l = 0; l < k; l++) {        if (next != null) {            next = next.next;        }else {            return null;        }    }    while (next != null){        pre = pre.next;        next = next.next;    }    return pre;}

链表是否有环、环的入口

1.快慢指针，快指针每次走两步，慢指针每次走一步

2.若在遍历链表的过程中，出现 快指针指向的节点等于慢指针指向的节点，说明链表有环，并且相遇的点一定在环中（不然不可能相遇）3.设定 链表头到环入口的距离为 x ，环入口到相遇点的距离为 a，环的总长度为 c，环相遇点到入口的距离为 b，则 a+b = c4.假设此时快慢指针在环内相遇，那么慢指针走过的距离 Step（low） = x + m * c + a （m为慢指针走过的圈数） ①快指针走过的距离 Step（fast） = x + n * c + a （n为快指针走过的圈数） ②Step（fast） = 2 * Step（low）③5.根据①②③，得到 x = c （n - 2 m - 1）+ b ，也就是说链表头到环入口的距离 x 等于 环的长度 c 的倍数 + b6.相遇时，此时若将慢（快）其中一个放到链表开头，然后开头的指针和环中的指针一起一步步走，那么开头的指针走 x 步时，环中的指针将走 k 圈 + b 步，此时 两指针再次相遇，并且相遇点位环入口点，即为所求

public static ListNode getCircleroot(ListNode head){    if (head == null || head.next == null){        return null;    }    ListNode slow = head;    ListNode fast = head;    while (fast != null && fast.next != null){        slow = slow.next;        fast = fast.next.next;        if (slow == fast){            // 相遇时 终止循环            break;        }    }    if (fast != slow){        return null;    }    fast = head;  // 将其中一个指针指向开头    while (fast != slow){        fast = fast.next;        slow = slow.next;    }    // 再次相遇时即为环入口点    return fast;}

欢迎加入学习交流群569772982，大家一起学习交流。