快慢指针 ——链表 | Leetcode 练习

1. 链表的中间结点
   
   给定一个头结点为 head 的非空单链表，返回链表的中间结点。
   如果有两个中间结点，则返回第二个中间结点。

返回链表的中间结点可以使用双指针法，也就是快慢指针。创建两个指针，同时从 head 结点出发，满指针走得慢，一次走一步，快指针走得快，等到快指针走到链表的末尾时，满指针刚好走到链表的一半，返回满指针指向的结点就是链表的中间结点。

class Solution {
    public ListNode middleNode(ListNode head) {
        // 快慢指针
        ListNode slow = head;
        ListNode fast = head;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
}

2. 删除链表的倒数第 N 个结点
   
   给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
   

使用快慢指针，两个指针同时遍历链表，由于需要找到倒数第n个结点，可以使快指针超前n个结点，这样当快指针走到链表末尾，慢指针就是倒数第n个结点。满指针与快指针相差n - 1个结点，为了方便删除，可以创建一个虚拟头结点，这样当快指针走到链表末尾时，慢指针指向倒数第 n 个结点的前驱节点，然后使用 slow.next = slow.next.next 删除倒数第 n 个结点。

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode pre = new ListNode(0);
        pre.next = head;
        ListNode fast = pre;
        ListNode slow = pre;
        while(n != 0) {
            fast = fast.next;
            n --;
        }
        while(fast != null && fast.next != null) {
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return pre.next;
    }
}