How to find the middle node of one linked list in one crawl (if the length of the list is not specified)

Question

I have a problem, for example: "How to find the middle node of one linked list in only one crawl, and the twist is that we do not know the number of nodes in the linked list?"

I have an answer like "take a vector and start pushing all the addresses of the nodes when and when you go through the linked list and increase the counter until you reach the end of the list." Therefore, at the end we can get the number of nodes in the list, and even if (counter / 2) or if odd (counter / 2 + counter% 2) gives the average node number, and with this we can get vectore.at(middlenodenumber) points to middle node. "

That's fine ... but it's a waste of memory storing the entire address of a very large linked list! So how can we find the best solution?

Answer 1

Following are the steps:

• Take the two pointers *p1 and *p2 , pointing to the head of the linked list
• Run the loop and increment *p2 , 2 times (with zero checks)
• If *p2 not null, then increment *p1 1 time
• When *p2 reaches zero; you have *p1 in the center

[Note: you can use iterators instead of a pointer if you are dealing with a container type reference list]

Answer 2

Say you have std::list<T> l .

 std::list<T>::iterator i = l.begin(); std::list<T>::iterator m = l.begin(); bool even = true; while (i != list.end()) { if (even) ++m; ++i; even = !even; } 

Now m select the middle of l .

Answer 3

You can use one loop with two iterators, for example it1 and it2 , where you increase it2 only every second iteration of the loop. Finish when it1 reaches the end of the list. it2 will now point to the middle element of the list.

Answer 4

Try the following:
You have 2 pointers. one points to the middle, and the other to the end, both indicate the beginning of the list at startup. Every second time that you successfully increment the end pointer, you increment the middle once until you finish the pointer to the end.

Answer 5

Use two pointers. Move the first pointer to two nodes and the second pointer to one node. When the first pointer reaches the end, the second pointer will point to the middle.

Answer 6

 // How to find the middle node of a single linked list in a single traversal // 1. The length of the list is not given // 2. If the number of nodes is even, there are two middle nodes, // return the first one. Node* MiddleNode(Node* const head) { if (!head) { return head; } Node* p1 = head, * p2 = head->next; while (p2 && p2->next) { p1 = p1->next; p2 = p2->next->next; } return p1; } 

Answer 7

 SLNode* mid(SLNode *head) { SLNode *one = head; SLNode *two = head; while(one != nullptr) { one = one->next; two = two->next; if(one != nullptr) { one = one->next; //two = two->next; } } return two; } 

try this code