有一带头结点的单链表L,其结点的data域的数据类型为整型。请(1)给出此单链表的数据结构定义;(2)设计算法将其拆分成一个非负整数单链表L1和一个负整数单链表L2
时间: 2024-09-23 12:15:07 浏览: 121
(1) 单链表的数据结构通常定义为一个节点类,包含数据域(data,用于存储整数值)和指针域(next,指向下一个节点)。在头结点的基础上,定义如下:
```cpp
// 如果是C++的模板类定义
template <typename T>
struct ListNode {
T data; // 存储整数
ListNode* next; // 指向下一个节点的指针
ListNode(T val = 0) : data(val), next(nullptr) {} // 构造函数
};
// 或者如果是Java的定义
class ListNode {
int data;
ListNode next;
public ListNode(int val) {
this.data = val;
this.next = null;
}
};
```
(2) 对于将给定的整数链表拆分成正数链表L1和负数链表L2,可以遍历整个链表,根据节点值的正负新建两个链表。这里是一个简单的算法描述:
```cpp
void splitLinkedList(ListNode<int>* head, ListNode<int>** l1, ListNode<int>** l2) {
*l1 = nullptr; *l2 = nullptr;
ListNode<int> current = head;
while (current != nullptr) {
if (current->data >= 0) {
if (*l1 == nullptr) {
*l1 = current;
} else {
(*l1)->next = current;
*l1 = current;
}
} else {
if (*l2 == nullptr) {
*l2 = current;
} else {
(*l2)->next = current;
*l2 = current;
}
}
current = current->next;
}
}
```
在这个算法中,`l1` 和 `l2` 分别是正链表和负链表的头指针。如果遇到正数,则在 `l1` 链表上继续添加新节点,反之则在 `l2` 链表上添加。
阅读全文