考研错题本——数据结构

1 绪论

【习题】

【解析】C、B

【习题】

【解析】A

【习题】

【解析】A

【习题】

【解析】C，有序表指出了表中数据时根据一定逻辑结构顺序排列的，值一种逻辑结构

【习题】

【解析】

2 线性表

【习题】

【解析】
数组和单链表的处理是一样的，这里给出 LeetCode 21 - 合并两个有序链表 迭代的解法，时间复杂度是 $O(m+n)$O(m+n)，空间复杂度是 $O(1)$O(1)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode newhead(0);
        ListNode *p = &newhead;
        while(l1&&l2)
        {
            if(l1->val > l2->val) swap(l1, l2);
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        }
        p->next = l1?l1:l2;
        return newhead.next;
    }
};

【习题】

【解法】

void difference(ListNode *A, ListNode *B){
	ListNode *p = A->next;
	ListNode *q = B->next;
	ListNode *pre = A;
	while(p!=nullptr && q!=nullptr)
	{
		if(p->val<q->val)
		{
			pre =p;
			p = p->next;	
		}
		else if(p->val>q->val) q = q->next;
		else 
		{
			pre->next = p->next;
			ListNode *tmp = p;
			p = p->next;
			delete tmp;
			tmp = nullptr;
		}
	}
}