Q.2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only acce

Q:Implement an algorithm to delete a node in the middle of a singlelinked list, given only access to that node.

A:雙指針，slow和fast， slow每次走一步，fast走兩步，找到中點删除即可。如果連結清單為偶數個點，那麼不删除

#include <iostream>
using namespace std;

struct ListNode {
    int val;
	ListNode *next;
 	ListNode(int x) : val(x), next(NULL) {}
 };
 
ListNode *init(int a[], int n) {
 	ListNode *head = NULL;
 	ListNode *p = NULL;
 	for (int i = 0; i < n; i++) {
 		ListNode *cur = new ListNode(a[i]);
 		if (i == 0) {
 			head = cur;
 			p = cur;
 		}
 		p->next = cur;
 		p = cur;
 	}
 	return head;
}

void reverse(ListNode *prev ,ListNode *begin) {
	ListNode *p = begin, *cur = begin->next, *next = cur->next;
    for (; cur; p = cur, cur = next, next = next?next->next:NULL) {
        cur->next = p;
    }
    prev->next = p;
    begin->next = NULL;
    return ;
}

ListNode *removeMiddle(ListNode *head) {
	if (!head || !head->next) {
		return NULL;
	}
	ListNode *prev = head;
	ListNode *slow = head;
	ListNode *fast = head;
	while (fast && fast->next) {
		prev = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	if (fast) {
		ListNode *t = prev->next;
		prev->next = prev->next->next;
		delete t;
	}
	return head;
}

void printList(ListNode *head) {
	ListNode *p = head;
	for( ; p; p = p->next) {
		cout<<p->val<<" ";
	}
	cout<<endl;
}

int main() {
	int a[5] = {1,2,3,2,1};
	ListNode *head1 = init(a, 5);
	printList(head1);
	head1 = removeMiddle(head1);
	printList(head1);
	return 0;
}