17
- 首先我们需要设计一个循环双链表的结构体和它的创建函数（可跳过）
#define ElemType int typedef struct DNode{ ElemType data; struct DNode *prior, *next; }DNode, *DLinkList; // 创建一个带头结点的循环双链表 CircularDoublyLinkedList DLinkList createCdlist(vector<int> data) { if (data.size() == 0) return NULL; DNode* head = (DLinkList)malloc(sizeof(DNode)); head->next = NULL; DNode* p = head; for (int i = 0; i < data.size(); i++) { DNode* q = (DNode*)malloc(sizeof(DNode)); q->data = data[i]; q->next = NULL; q->prior = p; // 前驱 p->next = q; p = q; } p->next = head; // 收尾 head->prior = p; return head; } void printList(DLinkList L) { DNode *head = L->next; while (head != L) { cout << head->data << " "; head = head->next; } puts(""); } 复制代码
- 头尾对比，只要有一个不同就不对称
- 注意循环条件
- 时间复杂度O(n)，空间复杂度O(1)
bool isSymmetry(DLinkList L) { // 1.创建两头的指针 DNode *p = L->next, *q = L->prior; // 2.向中间遍历 while (p != q && p->next != q) { if (p->data == q->data) { p = p->next; q = q->prior; } else { // 如果有一个值不等则不对称 return false; } } // 3.循环结束证明对称 return true; } 复制代码
18
- 循环单链表结构体及创建函数（可跳过）
// 创建一个带头结点的循环单链表 LinkList createHeadList(vector<int> data) { if (data.size() == 0) return NULL; LNode* head = (LinkList)malloc(sizeof(LNode)); head->next = NULL; LNode* p = head; for (int i = 0; i < data.size(); i++) { LNode* q = (LNode*)malloc(sizeof(LNode)); q->data = data[i]; q->next = NULL; p->next = q; p = q; } p->next = head; // 最后指向头指针 return head; } void printList(LinkList L) { LNode *head = L->next; while (head != L) { cout << head->data << " "; head = head->next; } puts(""); } 复制代码
- 找到h1的尾结点链接
- 找到h2的尾结点指向h1头结点
- 时间复杂度O(len1+len2)，也就是O(n)，空间复杂度O(1)
void linkTwoLists(LinkList h1, LinkList h2) { // 1.创建工作指针 LNode *p1 = h1->next, *p2 = h2->next; // 2.找到h1的尾结点 while (p1->next != h1) { p1 = p1->next; } // 3.链接h2 p1->next = p2; // 4.找到h2的尾结点，指向h1 while(p2->next != h2) { p2 = p2->next; } p2->next = h1; }
