关于链表的几种解法。快慢指针。
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; } }