使用快慢指针实现链表找中点问题

要求

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

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

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

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

注：比如1->2->3->4链表，上中点为2，下中点为3。

C++ 版本

/************************************************************************* > File Name: 021.快慢指针.cpp > Author: Maureen > Mail: [email protected] > Created Time: 四 6/ 9 16:32:14 2022 ************************************************************************/

#include <iostream>
#include <vector>
using namespace std;

class Node {
    
public:
    int value;
    Node *next;

    Node(int v) : value(v), next(nullptr) {
      }
};

//1. 给定链表头节点，奇数长度返回中点，偶数长度返回上中点
Node *midOrUpMidNode(Node *head) {
    
    if (head == nullptr) return head;

    Node *slow = head;
    Node *fast = head->next;
    while (fast != nullptr && fast->next != nullptr) {
    
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

//2. 给定链表头结点，奇数长度返回中点，偶数长度返回下中点
Node *midOrDownMidNode(Node *head) {
    
    if (head == nullptr) return head;

    Node *slow = head;
    Node *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
    
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


//3. 给定链表头节点，奇数长度返回中点前一个，偶数长度返回上中点前一个
Node *midOrUpMidPreNode(Node *head) {
    
    if (head == nullptr || head->next == nullptr) return nullptr;

    Node *slow = head;
    Node *fast = head->next->next;
    while (fast != nullptr && fast->next != nullptr && fast->next->next != nullptr) {
    
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

//4. 给定链表头结点，奇数长度返回中点前一个，偶数长度返回下中点前一个
Node *midOrDownMidPreNode(Node *head) {
    
    if (head == nullptr || head->next == nullptr) return nullptr;

    Node *slow = head;
    Node *fast = head->next;

    while (fast != nullptr && fast->next != nullptr && fast->next->next != nullptr) {
    
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}


//For test
Node *right1(Node *head) {
    
    if (head == nullptr) return nullptr;

    Node *cur = head;

    vector<Node *> arr;
    while (cur != nullptr) {
    
        arr.push_back(cur);
        cur = cur->next;
    }
    return arr[(arr.size() - 1) / 2];
}


Node *right2(Node *head) {
    
    if (head == nullptr) return nullptr;
    Node *cur = head;

    vector<Node *> arr;
    while (cur != nullptr) {
    
        arr.push_back(cur);
        cur = cur->next;
    }
    return arr[arr.size() / 2];
}


Node *right3(Node *head) {
    
    if (head == nullptr) return nullptr;

    Node *cur = head;
    vector<Node*> arr;
    while (cur != nullptr) {
    
        arr.push_back(cur);
        cur = cur->next;
    }

    return arr[(arr.size() - 3) / 2];
}

Node *right4(Node *head) {
    
    if (head == nullptr) return nullptr;
    Node *cur = head;
    vector<Node *> arr;
    while (cur != nullptr) {
    
        arr.push_back(cur);
        cur = cur->next;
    }
    return arr[(arr.size() - 2) / 2];
}


int main() {
    
    Node *test = nullptr;
    test = new Node(0);
    test->next = new Node(1);
    test->next->next = new Node(2);
    test->next->next->next = new Node(3);
    test->next->next->next->next = new Node(4);
    test->next->next->next->next->next = new Node(5);
    test->next->next->next->next->next->next = new Node(6);
    test->next->next->next->next->next->next->next = new Node(7);
    test->next->next->next->next->next->next->next->next = new Node(8);
    test->next->next->next->next->next->next->next->next->next = new Node(9);
    Node *ans1 = nullptr;
    Node *ans2 = nullptr;

    ans1 = midOrUpMidNode(test);
    ans2 = right1(test);

    cout << "=======midOrUpMidNode vs. right1==========" << endl;
    cout << (ans1 != nullptr ? ans1->value : -1) << endl;
    cout << (ans2 != nullptr ? ans2->value : -1) << endl;


    ans1 = midOrDownMidNode(test);
    ans2 = right2(test);
    cout << "=======midOrDownMidNode vs. right2==========" << endl;
    cout << (ans1 != nullptr ? ans1->value : -1) << endl;
    cout << (ans2 != nullptr ? ans2->value : -1) << endl;


    ans1 = midOrUpMidPreNode(test);
    ans2 = right3(test);
    cout << "=======midOrUpMidPreNode vs. right3==========" << endl;
    cout << (ans1 != nullptr ? ans1->value : -1) << endl;
    cout << (ans2 != nullptr ? ans2->value : -1) << endl;


    ans1 = midOrDownMidPreNode(test);
    ans2 = right4(test);
    cout << "=======midOrDownMidPreNode vs. right4==========" << endl;
    cout << (ans1 != nullptr ? ans1->value : -1) << endl;
    cout << (ans2 != nullptr ? ans2->value : -1) << endl;

    return 0;
}

Java 版本

public class LinkedListMid {
    

	public static class Node {
    
		public int value;
		public Node next;

		public Node(int v) {
    
			value = v;
		}
	}

	// head 头
	public static Node midOrUpMidNode(Node head) {
    
		if (head == null || head.next == null || head.next.next == null) {
    
			return head;
		}
		// 链表有3个点或以上
		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;
	}

	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;
	}

	public static Node midOrUpMidPreNode(Node head) {
    
		if (head == null || head.next == null || head.next.next == null) {
    
			return null;
		}
		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;
	}

	public static Node midOrDownMidPreNode(Node head) {
    
		if (head == null || head.next == null) {
    
			return null;
		}
		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;
	}

	public static Node right1(Node head) {
    
		if (head == null) {
    
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
    
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 1) / 2);
	}

	public static Node right2(Node head) {
    
		if (head == null) {
    
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
    
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get(arr.size() / 2);
	}

	public static Node right3(Node head) {
    
		if (head == null || head.next == null || head.next.next == null) {
    
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
    
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 3) / 2);
	}

	public static Node right4(Node head) {
    
		if (head == null || head.next == null) {
    
			return null;
		}
		Node cur = head;
		ArrayList<Node> arr = new ArrayList<>();
		while (cur != null) {
    
			arr.add(cur);
			cur = cur.next;
		}
		return arr.get((arr.size() - 2) / 2);
	}

	public static void main(String[] args) {
    
		Node test = null;
		test = new Node(0);
		test.next = new Node(1);
		test.next.next = new Node(2);
		test.next.next.next = new Node(3);
		test.next.next.next.next = new Node(4);
		test.next.next.next.next.next = new Node(5);
		test.next.next.next.next.next.next = new Node(6);
		test.next.next.next.next.next.next.next = new Node(7);
		test.next.next.next.next.next.next.next.next = new Node(8);

		Node ans1 = null;
		Node ans2 = null;

		ans1 = midOrUpMidNode(test);
		ans2 = right1(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidNode(test);
		ans2 = right2(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrUpMidPreNode(test);
		ans2 = right3(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

		ans1 = midOrDownMidPreNode(test);
		ans2 = right4(test);
		System.out.println(ans1 != null ? ans1.value : "无");
		System.out.println(ans2 != null ? ans2.value : "无");

	}
}