赞
踩
提示:链表创建、链表反转、链表合并,完整输入输出c++
给定一个单链表,将链表两两首尾相连,如1 2 3 4 5 6,变成1 6 2 5 3 4
将链表拆分成两段,后一段反转之后,再将两端链表合并
//链表折叠 #include <iostream> using namespace std; struct listNode { int val; listNode* next; listNode(int value) :val(value), next(nullptr) {} }; // 输入链表 void input(listNode* head, int num) { listNode* cur = head; for (int i = 1; i <= num; i++) { listNode* newNode = new listNode(i); cur->next = newNode; cur = cur->next; } } // 打印链表 void printList(const listNode* cur) { while (cur) { cout << cur->val << " "; cur = cur->next; } cout << endl; } //分割链表 listNode* findHalfhead(listNode* head, int num) { listNode* cur = head; listNode* halfHead = cur; for (int i = 0; i <= (num / 2); i++) { cur = cur->next; halfHead = cur; } return halfHead; } //反转链表 listNode* reverseList(listNode* head) { listNode* tmp(0); listNode* cur = head; listNode* pre = nullptr; while (cur) { tmp = cur->next; cur->next = pre; pre = cur; cur = tmp; } return pre; } //合并链表 listNode* combineList(listNode* head1, listNode* head2) { listNode* cur1 = head1; listNode* cur2 = head2; while (cur2->next) { listNode* tmp1 = cur1->next; listNode* tmp2 = cur2->next; cur1->next = cur2; cur2->next = tmp1; cur1 = tmp1; cur2 = tmp2; } return head1; } int main() { int num; cin >> num; listNode* head = new listNode(0); input(head, num); listNode* halfHead = findHalfhead(head, num); printList(head); printList(halfHead); listNode* end = reverseList(halfHead); printList(head); printList(end); listNode* finalHead = combineList(head, end); printList(finalHead); system("pause"); return 0; }
时间复杂度:O(n)
空间复杂度:不分析了,引用的子函数较多
这一题考核的链表知识比较全面,算是将链表的创建、插入、删除、遍历都包括在内,是一道经典的链表综合题,在面试中经常遇到。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。