设计一段算法,在一个单链表中值为y的结点前插入一个值为x的结点,就是使值为x的结点成为值为y的结点的前驱结点
时间: 2023-04-12 12:01:14 浏览: 135
链表插入结点算法
可以使用双指针法遍历单链表,找到值为y的结点,然后在它前面插入值为x的结点。具体实现如下:
ListNode* insertNode(ListNode* head, int x, int y) {
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* prev = dummy;
ListNode* curr = head;
while (curr) {
if (curr->val == y) {
ListNode* node = new ListNode(x);
prev->next = node;
node->next = curr;
break;
}
prev = curr;
curr = curr->next;
}
return dummy->next;
}
其中,dummy结点是为了方便处理头结点而添加的,prev指向当前结点的前驱结点,curr指向当前结点。如果找到值为y的结点,就在它前面插入值为x的结点,并返回头结点。如果遍历完整个链表都没有找到值为y的结点,就返回原来的头结点。
阅读全文