线性链表的结点移动
时间: 2023-07-11 13:10:26 浏览: 49
在线性链表中,结点的移动可以分为两种情况:
1. 删除结点:如果要删除某个结点,可以先找到该结点的前驱结点,然后将前驱结点的next指针指向该结点的后继结点,最后释放该结点的内存空间即可。
例如,假设要删除链表中的结点B,可以先找到结点A,然后将A的next指针指向C,最后释放B的内存空间。
```
A B C
↓ ↓ ↓
+---+---+---+
| 1 | 2 | 3 |
+---+---+---+
```
2. 插入结点:如果要在某个结点后面插入一个新的结点,可以先创建新的结点,然后将该结点的next指针指向该结点的后继结点,再将前驱结点的next指针指向该结点即可。
例如,假设要在链表中的结点B后面插入一个新的结点D,可以先创建结点D,然后将D的next指针指向C,最后将B的next指针指向D。
```
A B C
↓ ↓
+---+---+---+---+
| 1 | 2 | D | 3 |
+---+---+---+---+
```
需要注意的是,在链表中移动结点要注意边界条件,例如链表为空或只有一个结点的情况,以及要移动的结点是头结点或尾结点的情况。同时还需要考虑线程安全等问题。
相关问题
删除线性链表倒数第i个结点
可以使用双指针法来解决这个问题。首先,让一个指针从链表的头部开始移动 i 个位置,然后让另一个指针从链表的头部开始移动,直到第一个指针到达链表的末尾。此时,第二个指针所指向的结点就是倒数第 i 个结点。然后,我们可以将该结点从链表中删除即可。
以下是示例代码:
```
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p = head, *q = head;
for (int i = 0; i < n; i++) {
p = p->next;
}
if (!p) {
return head->next;
}
while (p->next) {
p = p->next;
q = q->next;
}
q->next = q->next->next;
return head;
}
```
这段代码实现了删除链表倒数第 n 个结点的功能。如果链表长度小于 n,直接返回 head->next 即可。
删除线性链表倒数第n个结点
可以使用双指针法来解决这个问题。首先,让一个指针指向链表的头部,另一个指针指向第n个结点。然后,让两个指针同时向后移动,直到第二个指针到达链表的末尾。此时,第一个指针所指向的结点就是要删除的结点。
具体实现可以参考以下代码:
```
struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
struct ListNode *p1 = head, *p2 = head;
for (int i = 0; i < n; i++) {
p2 = p2->next;
}
if (!p2) {
return head->next;
}
while (p2->next) {
p1 = p1->next;
p2 = p2->next;
}
p1->next = p1->next->next;
return head;
}
```
这段代码实现了删除链表倒数第n个结点的功能。如果链表长度小于n,则直接返回头结点的下一个结点。否则,使用双指针法找到要删除的结点,并将其从链表中删除。