单链表头插法和尾插法
时间: 2023-11-08 20:06:51 浏览: 57
单链表是一种常见的数据结构,它由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。单链表有两种插入方式:头插法和尾插法。
头插法是将新节点插入到链表的头部,即新节点的 next 指针指向原来的头节点,然后将新节点设置为头节点。代码实现如下:
```python
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def insertAtHead(head: ListNode, val: int) -> ListNode:
new_node = ListNode(val)
new_node.next = head
return new_node
```
尾插法是将新节点插入到链表的尾部,即找到链表的最后一个节点,将其 next 指针指向新节点。代码实现如下:
```python
def insertAtTail(head: ListNode, val: int) -> ListNode:
new_node = ListNode(val)
if not head:
return new_node
cur = head
while cur.next:
cur = cur.next
cur.next = new_node
return head
```
相关问题
c语言单链表头插法和尾插法
单链表是由一组节点组成的数据结构,每个节点包含两部分:一个数据域和一个指针域。其中,数据域用来存储节点的数据,指针域则指向下一个节点(如果有的话)。单链表的头节点通常不存储数据,只是作为链表的起点。
头插法即在链表头部插入新的节点,而尾插法则是在链表尾部插入新的节点。两种插入方法的实现方式如下:
头插法:
```c
// 定义节点结构体
typedef struct ListNode {
int val; // 节点的数据域
struct ListNode *next; // 节点的指针域
} ListNode;
ListNode* createNode(int val) {
// 创建一个新节点
ListNode* node = (ListNode*)malloc(sizeof(ListNode));
node->val = val;
node->next = NULL;
return node;
}
ListNode* insertAtHead(ListNode* head, int val) {
ListNode* node = createNode(val); // 创建新节点
node->next = head; // 将新节点插入到头部
return node; // 返回新的头部节点
}
```
尾插法:
```c
ListNode* insertAtTail(ListNode* head, int val) {
ListNode* node = createNode(val); // 创建新节点
if (head == NULL) { // 如果链表为空
return node; // 直接将新节点作为头部节点
}
ListNode* cur = head;
while (cur->next != NULL) { // 找到链表的尾部节点
cur = cur->next;
}
cur->next = node; // 将新节点插入到尾部
return head; // 返回头部节点
}
```
需要注意的是,插入节点时要判断链表是否为空,否则会出现空指针异常。
不带头结点的单链表头插法和尾插法建立
好的,我可以为你介绍一下不带头结点的单链表头插法和尾插法的建立方法。
不带头结点的单链表是指链表的第一个节点就是存储数据的节点,而不是一个空的头结点。
首先,我们先来介绍头插法建立单链表的方法。具体步骤如下:
1. 定义一个指向链表头节点的指针变量head,初始化为NULL。
2. 读入一个新节点的数据,创建一个新节点并用该数据进行初始化。
3. 将新节点插入到链表的最前面,使其成为新的头节点。具体操作为:将新节点的next指针指向head,然后将head指针指向新节点。
4. 重复步骤2和3,直到读入的数据为结束标志。
头插法建立单链表的示意图如下所示:
```
NULL <- 1 <- 2 <- 3 <- NULL
```
接下来,我们再来介绍尾插法建立单链表的方法。具体步骤如下:
1. 定义一个指向链表头节点的指针变量head,初始化为NULL。
2. 定义一个指向链表尾节点的指针变量tail,初始化为NULL。
3. 读入一个新节点的数据,创建一个新节点并用该数据进行初始化。
4. 如果head指针为NULL,则将head和tail指针都指向新节点。
5. 如果head指针不为NULL,则将tail节点的next指针指向新节点,然后将tail指针指向新节点。
6. 重复步骤3到5,直到读入的数据为结束标志。
尾插法建立单链表的示意图如下所示:
```
NULL <- 1 <- 2 <- 3 <- NULL
```