写一算法求带头结点的单链表L的长度

1. 初始化计数器count为0，指针p指向头结点L->next。
2. 当p不为空时，执行以下步骤：
a. 计数器count加1。
b. 将p指向下一个节点p->next。
3. 返回计数器count的值，即为链表L的长度。

算法实现：

int getLength(ListNode* L) {
    int count = 0;
    ListNode* p = L->next;
    while (p != NULL) {
        count++;
        p = p->next;
    }
    return count;
}

其中，ListNode为链表节点的结构体，包含数据域和指针域。头结点L为一个不存储数据的节点，其指针域指向链表的第一个节点。

相关问题

试写一算法求带头结点的单链表L的长度。

可以使用以下算法求带头结点的单链表L的长度：

1. 初始化计数器count为0，指针p指向L的头结点。
2. 如果p所指的结点不为空，将count加1。
3. 将p指向下一个节点。
4. 重复步骤2-3，直到p所指的结点为空。
5. 返回计数器count，即L的长度。

以下是使用C语言实现该算法的代码：

int getLength(ListNode *head) {
int count = 0;
ListNode *p = head->next;
while(p) {
count++;
p = p->next;
}
return count;
}

其中ListNode结构体表示单链表的节点：

struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};

c语言用带头结点的单链表表示整数集合。设计一个算法，求两个集合A和B的并集。要求不破坏原有的单链表A和B。2. 假设带头结点单链表的长度大于3。设计一个算法，让一个工作指针p指向链表中后面的第三个结点。要求只扫描一遍单链表

在C语言中，使用带头节点的单链表表示整数集合，可以设计这样的数据结构：

typedef struct ListNode {
    int data;
    struct ListNode* next;
} ListNode;

ListNode* createSet(int num) {
    ListNode* head = (ListNode*)malloc(sizeof(ListNode));
    if (head == NULL) return NULL;
    head->data = num;
    head->next = NULL;
    return head;
}

void insertToList(ListNode** head, int num) {
    ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
    if (newNode == NULL) return;
    newNode->data = num;
    newNode->next = *head;
    *head = newNode;
}

为了求两个链表A和B的并集，我们可以遍历两个链表，将不在对方链表中的元素添加到结果链表：

ListNode* unionLists(ListNode* listA, ListNode* listB) {
    ListNode* resultHead = NULL, *currentA = listA, *currentB = listB;
    
    while (currentA && currentB) {
        if (currentA->data < currentB->data) {
            if (!resultHead) {
                resultHead = currentA;
            } else {
                currentA->next = resultHead;
            }
            currentA = currentA->next;
        } else if (currentB->data < currentA->data) {
            // 类似于处理currentA的情况，只是交换currentA和currentB
            currentB = currentB->next;
        } else {
            // 如果值相等，跳过当前元素
            currentA = currentA->next;
            currentB = currentB->next;
        }
    }

    // 将剩余的列表元素追加到结果中
    while (currentA) {
        if (!resultHead) {
            resultHead = currentA;
        } else {
            currentA->next = resultHead;
        }
        currentA = currentA->next;
    }

    if (currentB) {
        currentB->next = resultHead;
    }

    return resultHead;
}

至于让一个工作指针p指向链表中后面的第三个结点，我们可以设置初始指针和移动指针的函数：

void advanceThirdElement(ListNode** p) {
    for (*p = (*p)->next; (*p)->next && (*p)->next->next; (*p) = (*p)->next);
}

// 示例用法
void movePToThird(ListNode* list) {
    ListNode* p = list->next;
    advanceThirdElement(&p);
}

这样，`p`就指向了链表A的第四个结点（因为头结点不算），如果链表长度大于3。