链表的中间节点

Question

我试图返回链表的中间节点，当节点数为偶数时它工作得很好，当节点数为奇数时，我看到的只是分段错误。最初，如果快速达到 NULL，我会返回慢速，但对于奇数个节点，它仍然失败。 我尝试了两个条件：1.如果快速达到NULL并且链表的长度是偶数：返回慢速 2.如果fast到达NULL且链表长度为奇数：返回slow->next。我还运行 gdb，它将段错误指向：fast = fast->next->next;在 middle_node(node *) 函数中。欣赏。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


typedef struct node
{
    // holds number of type int
    int number;
    // holds pointer to node of the same type
    struct node *next;
} node;

int count = 0;    

// insert/tuck new node into the existing linked list
node *insert(node *, int);

// delete entire linked list
bool destroy(node *);

// return size of  linked-list
int list_size(node *);

// return middle node of linked list
node *middle_node(node *);

int main(void)
{
    // declare head node
    node *list = NULL;
    
    // inserting  into linked list with a loop var 
    for (int i = 0; i < 11; i++)
    {
        list = insert(list, 1 + i);    
    }

    node *middle = NULL;
    middle = middle_node(list);
    printf("node: %p, value: %i\n", middle, middle->number);
    
    // destroy/free heaps
    destroy(list);
 }


// insert/tuck new node into the existing linked list
node *insert(node *head, int x)
{
    // 1 dynamically allocate space for the new node
    node *new = (node *)malloc(sizeof(node));
    // 2 check to make sure we didnt run out of memory
    if (new == NULL)
    {
        return 0; // NULL
    }
    // 3 populate and insert the node at the beginning of the linked list
    new->number = x;
    // 3B arrange/connect the pointers in the correct order
    // connect new element's next pointer to head first
    new->next = head;
    // set head to point to new element
    head = new;
    // 4 return a pointer to the new head of linked list
    return head;
}

// delete/free entire singly linked list
bool destroy(node *head)
{
    // 1 if youve reach a NULL pointer, stop
    if (head != NULL)
    {
        // 2 else: delete the rest of the list (recursively)
        destroy(head->next);
        // 3 free the current node
        free(head);
        return true;
    }
    return false;
}

// return size of linked list
int list_size(node *head)
{
    // return size of linked list
    // temp points to head of list
    node *temp = head;
    int size = 0;
    while (temp != NULL)
    {
        size += 1;
        temp = temp->next;
    }
    return size;
}

// return middle node of linked list
node *middle_node(node *head)
{
    // declare to pointers fast and slow of type node *
    if (head != NULL)
    {
        node *slow = NULL, *fast = NULL, *current = NULL;
        slow = head;
        fast = head;
        current = head;
        while (current != NULL)
        {
            count++;
            // one step at a time
            slow = slow->next;
            // two step at a time
            fast = fast->next->next;            
            
            // when fast points to last node
            if ((fast == NULL) && (list_size(head) % 2 == 1))
            {
                // return slow as the middle node 
                return slow->next;
            }
            if ((fast == NULL) && (list_size(head) % 2 == 0))
            {
                return slow;
            }

            // else update current node one step forward
            current = current->next;
        }
    }
    else
    {
        // return NULL otherwise
        return NULL;
    }
}

Answer 1

您的快速跑步者，

fast = fast->next->next;

，在链接列表包含奇数个元素的情况下会尝试取消引用

NULL

。考虑一下列表是否只包含 one 元素。

fast->next

将变为

NULL

，并且

fast->next->next

将取消引用

NULL

，这会导致程序出现 未定义的行为。

在继续取消引用

fast->next

之前，您需要检查取消引用

NULL

是否返回非

fast->next->next

。它可能看起来像这样：

node *middle_node(node *head) {
    node *slow = head;
    while(head && head->next) {
        slow = slow->next;
        head = head->next->next;
    }
    return slow;
}

演示

---

您可以利用您的

list_size

函数来简化这一过程 - 它会遍历列表 1.5 次，就像您的慢速和快速跑步者所做的那样。

node *middle_node(node *head) {
    int size = list_size(head) / 2;
    while(size--) head = head->next;    
    return head;
}

演示