首页 > 代码库 > 单链表的算法题
单链表的算法题
单链表很简单,就是一些细节要注意。
多练练现场纸上手写。
#include <iostream> using namespace std; struct node { int key; node * next; node () : key(-1), next(NULL) {} node (int n) : key(n), next(NULL) {} }; void print (node * head) { while (head) { cout << head->key << " "; head = head->next; } cout << endl; } node * reverse (node * head) { if (head == NULL || head-> next == NULL) { return head; } node * pre = NULL; node * cur = head; node * next = NULL; while (cur) { next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } node * reverse (node * head, int k) { if (head == NULL || head-> next == NULL) { return head; } node * pre = NULL; node * cur = head; node * next = NULL; int i = 0; while (cur && i<k) { next = cur->next; cur->next = pre; pre = cur; cur = next; i++; } if (cur == NULL) { return pre; } node * new_head = pre; pre = NULL; while (cur) { next = cur->next; cur->next = pre; pre = cur; cur = next; } head->next = pre; return new_head; } node* pair_swap (node * head) { if (head == NULL || head-> next == NULL) { return head; } node tmp_head; node* pre = &tmp_head; node* first = head; while (first && first->next) { node* second = first->next; first->next = second->next; second->next = first; pre->next = second; pre = first; first = first->next; } return tmp_head.next; } int main () { int key; node * head = NULL; while (cin >> key) { node * cur = new node(key); cur->next = head; head = cur; } print (head); head = reverse(head); print (head); head = reverse(head, 3); print (head); head = pair_swap(head); print (head); }
sample input:
8 7 6 5 4 3 2 1
sample output:
1 2 3 4 5 6 7 8 //原始链表
8 7 6 5 4 3 2 1 //翻转链表
6 7 8 1 2 3 4 5 //前k个翻转,后面的再翻转
7 6 1 8 3 2 5 4 //两两交互相邻元素
单链表的算法题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。