无头结点单链表的创建和初始化
时间: 2023-05-14 12:04:45 浏览: 147
创建无头结点单链表的方法是先定义一个结构体表示链表中的每个节点,然后定义一个指向该结构体的指针作为链表的头指针。初始化时,将头指针指向 NULL 即可。
以下是示例代码:
```
struct Node {
int data;
struct Node *next;
};
struct Node *head = NULL; // 头指针初始化为 NULL
// 添加节点的函数
void addNode(int data) {
struct Node *newNode = malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
if (head == NULL) {
head = newNode;
} else {
struct Node *p = head;
while (p->next != NULL) {
p = p->next;
}
p->next = newNode;
}
}
```
在上面的代码中,addNode 函数用于向链表中添加节点。如果链表为空,直接将头指针指向新节点;否则,遍历链表找到最后一个节点,将其 next 指针指向新节点。
注意,这里的链表是无头结点的,因此在遍历链表时需要特别处理头指针。
相关问题
怎么用python创建无头结点的单链表
可以使用Python中的类来表示单链表,每个节点包含数据和指向下一个节点的指针。无头结点的单链表通常需要在插入和删除节点时特别处理。
下面是一个示例代码,创建一个无头结点的单链表,并添加几个节点:
```python
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def add(self, data):
new_node = Node(data)
if not self.head:
self.head = new_node
else:
current_node = self.head
while current_node.next:
current_node = current_node.next
current_node.next = new_node
linked_list = LinkedList()
linked_list.add(1)
linked_list.add(2)
linked_list.add(3)
```
在上面的示例中,我们定义了两个类,一个是节点类Node,一个是单链表类LinkedList。每个节点包含一个数据和一个指向下一个节点的指针。单链表类包含一个头节点,初始值为None,表示一个空链表。我们提供了一个add()方法来添加新节点。
在add()方法中,如果链表为空,则将新节点设置为头节点。否则,我们遍历链表找到最后一个节点,并将新节点添加到最后一个节点的next属性中。
注意,由于这是一个无头结点的单链表,我们需要特别处理在链表开头插入节点的情况。在这种情况下,我们需要将新节点设置为头节点,并将它的next属性指向原来的头节点。在删除节点时,我们需要特别处理删除头节点的情况。
编写一个可以删除无头结点单链表的第i个结点的代码
假设我们已经有了一个单链表的头节点 `head`,我们可以按照以下步骤删除第 `i` 个结点:
1. 如果 `i` 为 0 或者 `head` 为 `null`,直接返回。
2. 如果 `i` 为 1,我们需要将 `head` 指向它的下一个结点,然后删除原来的头结点。
3. 如果 `i` 大于 1,我们需要遍历链表找到第 `i-1` 个结点,并记录它的位置为 `prev`。如果 `prev` 为 `null` 或者 `prev.next` 为 `null`,直接返回。否则,我们可以通过 `prev.next = prev.next.next` 来删除第 `i` 个结点。
下面是代码实现:
```java
public void deleteNode(ListNode head, int i) {
if (i == 0 || head == null) {
return;
}
if (i == 1) {
head = head.next;
return;
}
ListNode prev = head;
for (int j = 1; j < i - 1 && prev != null && prev.next != null; j++) {
prev = prev.next;
}
if (prev == null || prev.next == null) {
return;
}
prev.next = prev.next.next;
}
```
需要注意的是,这里我们传入的是头结点 `head`,而不是第一个结点。因此在删除头结点时需要更新 `head` 的值。另外,在遍历链表时,我们需要保证 `prev` 和 `prev.next` 都不为 `null`,否则可能会引起空指针异常。