关于链表的几种解法。快慢指针。

关于链表的几种解法。快慢指针。

package algorithmoftenuse;

/**
 * 链表问题：
 * 1.返回奇数长度的中点，偶数长度的上中点
 * 2.返回奇数长度的中点，偶数长度的下中点
 * 3.返回奇数长度中点的前一个，偶数长度的上中点前一个
 * 4.返回奇数长度中点的前一个，偶数长度的下中点的前一个
 */
public class LinkedListMid {

    public static class Node{
        public int value;
        public Node next;
        public  Node(int v){
            this.value = v;
        }
    }


    /**
     * 返回奇数长度的中点，偶数长度的上中点
     * @param head
     * @return
     */
    public static Node midOrUpMidNode(Node head){
        if (head == null || head.next == null || head.next.next == null){
            //没有节点、只有一个节点、有两个节点的情况
            return head;
        }

        //链表有三个及三个以上的节点
        //使用快慢指针
        Node slow = head.next;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 返回奇数长度的中点，偶数长度的下中点
     * @param head
     * @return
     */
    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;
    }


    /**
     * 返回奇数长度中点的前一个，偶数长度的上中点
     * @param head
     * @return
     */
    public static Node midOrMidPreNode(Node head){
        if (head == null || head.next == null || head.next.next == null){
            return head;
        }
        //三个节点及三个节点以上的情况
        Node slow = head;
        Node fast = head.next.next;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }


    /**
     * 返回奇数长度中点的前一个，偶数长度的下中点的前一个
     * @param head
     * @return
     */
    public static Node midOrMidDownNode(Node head){
        if (head == null || head.next == null){
            return head;
        }
        if (head.next.next == null){
            return head;
        }
        //三个节点及三个节点以上的情况
        Node slow = head;
        Node fast = head.next;
        while (fast.next != null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

}