链表问题

1、快慢指针问题

1、 输入链表头结点，奇数长度返回中点，偶数长度返回上中点

1 3 5 2 7 返回 5；1 3 2 7 返回 3

2、 输入链表头结点，奇数长度返回中点，偶数长度返回中下点

1 3 5 2 7 返回 5；1 3 2 7 返回 2

3、 输入链表头结点，奇数长度返回中点前一个，偶数长度返回上中点前一个

1 3 5 2 7 返回 3；1 3 2 7 返回 1

4、 输入链表头结点，奇数长度返回中点前一个，偶数长度返回下中点前一个

1 3 5 2 7 返回 3；1 3 2 7 返回 3

2、原理与案例

2.1 原理

• 利用一快一慢指针的步速差，实现快指针（Fast，简称F）指向链表最后可指向的节点时，慢指针（Slow，简称S）刚好移动到目标节点（如上所例举，目标节点可变）
• 令F每次向后移动两个节点，S每次向后移动一个节点，形成步速差
• 核心是根据具体问题合理构建快慢指针的函数关系式，使其在以下四种情况下都能满足S为返回结果的指针
  • 当F.next==null时，此时链表长度为F
    • 当F为偶数时，目标值指针为S
    • 当F为奇数时，目标值指针为S
  • 当F.next.next==null时，此时链表长度为F+1
    • 当F为偶数时，目标值指针为S
    • 当F为奇数时，目标值指针为S
• 而根据以上的四个关系约束，最后的结果可以确定F与S的函数关系，以及F奇偶性，

• 根据以上结果即可知道F和S的起始位置（令F为最小的起始位置，根据F与S的函数关系式即可得出S的起始位置），最后当F指针不能继续后移时，S指向的就是目标值

  2.2 案例

• 以第二例为例

  // 输入链表头结点，奇数长度返回中点，偶数长度返回中下点
  // 定义L为链表长度，F为快指针，S为慢指针
  // 假设指针指向的位置以节点的序号为值，如果F指向的是第五个节点，就认为F==5
  //1.当F为偶数时，L=F,返回中下点
    res=S=F/2+1
  //1.当F为偶数时，L=F+1，返回中点
  res=S=(F+1)/2+1
  //1.当F为奇数时，L=F，返回中点
  res=S=F/2+1
  //1.当F为奇数时，L=F+1，返回中下点
    res=S=(F+1)/2+1

  • 当F为偶数时，两个res的值是相等的
  • 当F为奇数时，两个res的值不等
  • 所以应该选择F为偶数，且满足：S=F/2+1
  • 故初始化：F=2，S=2 ，令F每次向后移动两个节点，S每次向后移动一个节点

  • 程序如下：

    public static class Node {
       public int value;
       public Node next;
       public Node(int v) {
           value = v;
       }
    }
    // 2、奇数长度返回中点，偶数长度返回中下点
    public static Node midOrDownMidNode(Node head) {
       if (head == null || head.next == null) {
           return head;
       }
       Node slow = head.next;
       Node fast = head.next;
       while (fast.next != null && fast.next.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow;
    }