C++程序查找给定链表的中间元素

给定一个单向链表，查找该链表的中间元素。

1. 例如，如果给定链表是1->2->3->4->5，则输出应为3。   如果节点数为偶数，则中间节点有两个，我们需要打印第二个中间元素。

2. 例如，如果给定链表是1->2->3->4->5->6，则输出应为4。

方法1：

遍历整个链表并计算节点数。

现在再次遍历列表，直到count/2的位置，返回在count/2的位置的节点。

//上述方法的C++程序
 
#include <iostream>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
};
 
class NodeOperation {
public:
    // 添加新节点的函数
    void pushNode(class Node** head_ref, int data_val)
    {
 
        // 分配一个节点
        class Node* new_node = new Node();
 
        // 存储数据
        new_node->data = data_val;
 
        // 将旧列表链接到新节点
        new_node->next = *head_ref;
 
        // 将头指针指向新节点
        *head_ref = new_node;
    }
 
    // 用于打印给定链表的实用函数
    void printNode(class Node* head)
    {
        while (head != NULL) {
            cout << head->data << "->";
            head = head->next;
        }
        cout << "NULL" << endl;
    }
 
    //获取链表长度的实用函数
    int getLen(class Node* head)
    {
        int len = 0;
        class Node* temp = head;
        while (temp) {
            len++;
            temp = temp->next;
        }
        return len;
    }
 
// 带有方法1的实现
    void printMiddle(class Node* head)
    {
 
        if (head) {
            // 获取长度
            int len = getLen(head);
            class Node* temp = head;
 
            // 遍历链表直到达到长度的一半
            int midIdx = len / 2;
            while (midIdx--) {
                temp = temp->next;
            }
            // temp将储存中间元素
            cout << "中间元素是[" << temp->data
                 << "]" << endl;
        }
    }
};
 
// 主函数
int main()
{
    class Node* head = NULL;
    class NodeOperation* temp = new NodeOperation();
    for (int i = 5; i > 0; i--) {
        temp->pushNode(&head, i);
        temp->printNode(head);
        temp->printMiddle(head);
    }
    return 0;
}

输出结果

5->NULL
中间元素是[5]
4->5->NULL
中间元素是[5]
3->4->5->NULL
中间元素是[4]
2->3->4->5->NULL
中间元素是[4]
1->2->3->4->5-> **中间元素是[3]**

时间复杂度 ：链表中节点数为n时，时间复杂度为O（n）。

辅助空间： O（1）

方法2：

使用两个指针遍历链表。

一个指针每次移动一个位置，另一个指针每次移动两个位置。当快指针到达末尾时，慢指针将到达链表的中间位置。

以下图像显示了代码中printMiddle函数的操作方式：

C++程序查找给定链表的中间元素

// 以上方法的C++程序
#include <iostream>
using namespace std;

class Node {
public:
    int data;
    Node* next;
};

class NodeOperation {
public:
    // 添加新节点的函数
    void pushNode(class Node** head_ref, int data_val)
    {

        // 分配节点
        class Node* new_node = new Node();

        // 放入数据
        new_node->data = data_val;

        // 将旧的链表连接到新节点
        new_node->next = *head_ref;

        // 将头指针移动到新节点
        *head_ref = new_node;
    }

    // 用于打印链表的辅助函数
    void printNode(class Node* head)
    {
        while (head != NULL) {
            cout << head->data << "->";
            head = head->next;
        }
        cout << "NULL" << endl;
    }

    void printMiddle(class Node* head)
    {
        struct Node* slow_ptr = head;
        struct Node* fast_ptr = head;

        if (head != NULL) {
            while (fast_ptr != NULL
                   && fast_ptr->next != NULL) {
                fast_ptr = fast_ptr->next->next;
                slow_ptr = slow_ptr->next;
            }
            cout << "中间元素是 ["
                  << slow_ptr->data << "]" << endl;
        }
    }
};

// 驱动程序
int main()
{
    class Node* head = NULL;
    class NodeOperation* temp = new NodeOperation();
    for (int i = 5; i > 0; i--) {
        temp->pushNode(&head, i);
        temp->printNode(head);
        temp->printMiddle(head);
    }
    return 0;
}

输出

5->NULL
中间元素是 [5]
4->5->NULL
中间元素是 [5]
3->4->5->NULL
中间元素是 [4]
2->3->4->5->NULL
中间元素是 [4]
1->2->3->4->5->NULL
中间元素是 [3]

时间复杂度: O(n)，其中n是给定链表中的节点数。

辅助空间: O(1)，不需要额外的空间，因此是一个常量。

方法3:

将中间元素初始化为头部，并将计数器初始化为0。从头部遍历列表，遍历时增加计数器，当计数器为奇数时将中间元素更改为mid->next。因此，中间元素只会移动总长度的一半。

#include <bits/stdc++.h>
using namespace std;
 
// Link list node
struct node {
    int data;
    struct node* next;
};
 
// Function to get the middle of
// the linked list
void printMiddle(struct node* head)
{
    int count = 0;
    struct node* mid = head;
 
    while (head != NULL) {
 
        // Update mid, when 'count'
        // is odd number
        if (count & 1)
            mid = mid->next;
 
        ++count;
        head = head->next;
    }
 
    // If empty list is provided
    if (mid != NULL)
        printf("The middle element is [%d]\n", mid->data);
}
 
void push(struct node** head_ref, int new_data)
{
 
    // Allocate node
    struct node* new_node
        = (struct node*)malloc(sizeof(struct node));
 
    // Put in the data
    new_node->data = new_data;
 
    // Link the old list off the new node
    new_node->next = (*head_ref);
 
    // Move the head to point to
    // the new node
    (*head_ref) = new_node;
}
 
// A utility function to print
// a given linked list
void printList(struct node* ptr)
{
    while (ptr != NULL) {
        printf("%d->", ptr->data);
        ptr = ptr->next;
    }
    printf("NULL\n");
}
 
// Driver code
int main()
{
 
    // Start with the empty list
    struct node* head = NULL;
    int i;
 
    for (i = 5; i > 0; i--) {
        push(&head, i);
        printList(head);
        printMiddle(head);
    }
    return 0;
}
 
// This code is contributed by ac121102```

输出

5->NULL
The middle element is [5]
4->5->NULL
The middle element is [5]
3->4->5->NULL
The middle element is [4]
2->3->4->5->NULL
The middle element is [4]
1->2->3->4->5->NULL
The middle element is [3]

时间复杂度： O(n)，其中n是给定链表中的节点数。

辅助空间： O(1)，不需要额外的空间，因此是一个常数。