已知指针LA和LB分别指向两个无头结点单链表的首元结点。要求编一算法实现,从表LA中删除自第i个元素起共len个元素后,将它们插入到表LB中第j个元素之前。
时间: 2024-03-04 20:48:47 浏览: 68
下面是一种实现方式:
```
// 定义单链表结点结构体
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
void deleteAndInsert(ListNode *LA, int i, int len, ListNode *LB, int j) {
if (i <= 0 || j <= 0 || len <= 0) return; // 参数不合法,直接返回
ListNode *p = LA;
int k = 1;
// 将p指向第i-1个结点
while (p != NULL && k < i) {
p = p->next;
k++;
}
if (p == NULL) return; // i超出了LA的长度,直接返回
ListNode *q = p->next;
p->next = NULL;
k = 1;
// 将q指向第i+len-1个结点
while (q != NULL && k < len) {
q = q->next;
k++;
}
if (q == NULL) return; // i+len-1超出了LA的长度,直接返回
ListNode *r = LB;
k = 1;
// 将r指向第j-1个结点
while (r != NULL && k < j) {
r = r->next;
k++;
}
if (r == NULL) return; // j超出了LB的长度,直接返回
ListNode *s = r->next;
r->next = p->next;
q->next = s;
}
```
算法思路:
首先,根据参数i将p指针指向表LA中第i-1个结点,根据参数j将r指针指向表LB中第j-1个结点,如果i或j超出了表的长度,则直接返回。
然后,通过p指针找到需要删除的第i个结点和需要删除的最后一个结点q,将p的next指针置为NULL,断开LA中需要删除的结点与前面的结点的链接。
接着,通过r指针找到插入位置的前一个结点r,将r的next指针指向需要删除的第i个结点,将需要删除的最后一个结点的next指针指向s,即插入位置的后一个结点。
最后,完成删除和插入操作。
阅读全文