1. 线性表总结
线性表的存储结构分为顺序和链式：
顺序存储结构可以快速读取元素，而链式需要进行元素的遍历
在插入与删除时，顺序存储结构需要进行移位的操作，而链式只需要进行查找，然后即可对元素插入与删除
2. 算法练习
2.1. 将两个递增的有序链表合并为⼀个有序链表
要求：结果链表仍然使⽤两个链表的存储空间，不另外占⽤其他的存储空间。表中不允许有重复的数据
示例：
La {1, 2, 3}Lb {3, 6, 9}Lc {1, 2, 3, 6, 9}
关键字：
递增有序链表
不允许有重复数据
保持递增关系：后插法
不占⽤额外空间：不允许新建额外结点来维持逻辑
代码实现：
public struct LinkedList<Element: Comparable>{
fileprivate class Node<T> {
var next : Node<T>?;
var data : T?;
init(){
}
init(data : T){
self.data = data;
self.next = nil;
}
deinit {
print(data == nil ? "头结点释放" : "值为\(data!)的Node释放");
}
}
fileprivate var _head : Node<Element>? = nil;
fileprivate var _r : Node<Element>? {
get{
var node = _head;
while(node?.next != nil){
node = node?.next;
}
return node;
}
};
public init(){
_head = Node<Element>();
}
mutating func pushTail(element : Element) -> Int{
let node = Node<Element>(data: element);
_r?.next = node;
return OK;
}
mutating func merge(list : LinkedList<Element>) {
var ptr1 = _head?.next;
var ptr2 = list._head?.next;
var ptr3 = _head;
while(ptr1 != nil && ptr2 != nil){
if(ptr1!.data! > ptr2!.data!){
ptr3?.next = ptr2;
ptr3 = ptr2;
ptr2 = ptr2?.next;
continue;
}
ptr3?.next = ptr1;
ptr3 = ptr1;
if(ptr1!.data! == ptr2!.data!){
ptr2 = ptr2?.next;
}
ptr1 = ptr1?.next;
}
if(ptr1 != nil || ptr2 != nil){
ptr3?.next = (ptr1 == nil) ? ptr2 : ptr1;
}
}
mutating func dealloc(){
_head = nil;
}
}
list1.merge(list: list2);
list2.dealloc();
ptr1指向链表A的首元结点，ptr2指向链表B的首元结点，ptr3执行链表A的头结点进行循环，要求
链表A和链表B都没有到达尾结点位置判断两个链表的值，取较小者存储到
ptr3如果相等，取
链表A的结点存储到ptr3循环结束，将还未到达结尾链表的后续元素拼接到
ptr3合并完成后，释放
链表B
2.2 求出链表A与链表B的交集，并存储在链表A中
已知两个链表A和B分别表示两个集合，其元素递增排列.。设计⼀个算法，⽤于求出A与B的交集，并存储在链表A中
示例：
La {2, 4, 6, 8}
Lb {4, 6, 8, 10}
La {4, 6, 8}
代码实现：
public struct LinkedList<Element: Comparable>{
mutating func merge(list : LinkedList<Element>) {
var ptr1 = _head?.next;
var ptr2 = list._head?.next;
var ptr3 = _head;
while(ptr1 != nil && ptr2 != nil){
if(ptr1!.data! < ptr2!.data!){
ptr1 = ptr1?.next;
continue;
}
if(ptr1!.data! > ptr2!.data!){
ptr2 = ptr2?.next;
continue;
}
ptr3?.next = ptr1;
ptr3 = ptr1;
ptr1 = ptr1?.next;
ptr2 = ptr2?.next;
}
ptr3?.next = nil;
}
}
ptr1指向链表A的首元结点，ptr2指向链表B的首元结点，ptr3执行链表A的头结点进行循环，要求
链表A和链表B都没有到达尾结点位置不相等，删除较小者
相等，链表A的结点存储到
ptr3循环结束，强行将
ptr3的后继指向空合并完成后，释放
链表B
2.3 将链表中所有结点的链接⽅向原地旋
设计⼀个算法，将链表中所有结点的链接⽅向原地旋转。要求仅仅利⽤原表的存储空间。换句话说，要求算法空间复杂度为O(1)
示例：
L = {0, 2, 4, 6, 8, 10}
逆转后: L = {10, 8, 6, 4, 2, 0}
代码实现：
public struct LinkedList<Element: Comparable>{
func reversal(){
var ptr = _head?.next;
_head?.next = nil;
while(ptr != nil){
let tmp = _head?.next;
_head?.next = ptr;
ptr = ptr?.next;
_head?.next?.next = tmp;
}
}
}
ptr指向首元结点，清空头结点的后继tmp存储原始的首元结点将
ptr存储在首元结点，将ptr指向它的后继将新插入的首元结点的后继指向
tmp
2.4 删除递增有序链表中值⼤于等于mink且⼩于等于maxk的所有元素
设计⼀个算法，删除递增有序链表中值⼤于等于mink且⼩于等于maxk的所有元素。mink、maxk是给定的两个参数，其值可以和表中的元素相同，也可以不同
代码实现：
public struct LinkedList<Element: Comparable>{
func deleteRange(min : Element, max : Element){
var ptr = _head;
var begin : Node<Element>?;
var end : Node<Element>?;
while(ptr != nil){
if(begin == nil && ptr?.next != nil && ptr!.next!.data! >= min && ptr!.next!.data! <= max){
begin = ptr;
}
if(ptr?.data != nil && ptr!.data! > max){
end = ptr;
break;
}
ptr = ptr?.next;
}
if(begin != nil){
begin?.next = end;
}
}
}
遍历链表，找到第一个大于等于
min，小于等于max的结点的前驱，存储到begin指针找到第一个大于
max的结点，存储到end指针，停止循环循环结束后，如果
begin不为空，将begin的后继赋值为end
2.5 将⼀维数组中保存的序列循环左移
设将n(n > 1)个整数存放到⼀维数组R中，试设计⼀个在时间和空间两⽅⾯都尽可能⾼效的算法，将R中保存的序列循环左移p个位置(0 < p < n)个位置。即将R中的数据由(x0, x1, ..., xn - 1)变换为(xp, xp + 1, ..., xn - 1, x0, x1, ..., xp - 1)
示例：
pre[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
n = 10, p = 3
pre[10] = {3, 4, 5, 6, 7, 8, 9, 0, 1, 2};
代码实现：
func reversal(list : inout [Int], begin : Int, end : Int) {
var i = begin;
var j = end;
while(i < j){
let tmp = list[i];
list[i] = list[j];
list[j] = tmp;
i += 1;
j -= 1;
}
}
let n = 10;
let p = 3;
var list : [Int] = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9];
reversal(list: &list, begin: 0, end: n - 1);
reversal(list: &list, begin: 0, end: n - p - 1);
reversal(list: &list, begin: n - p, end: n - 1);
for i in 0 ..< n {
print("\(list[i])");
}
实现
reversal方法，将数组中指定范围内元素逆置将整个数组逆置
将数组从
0至n - p - 1位置的元素逆置将数组从
n - p至结尾位置的元素逆置
2.6 找出数组元素中的主元素
已知⼀个整数序列A = (a0, a1, a2, ... an - 1)，其中(0 <= ai <= n)，(0 <= i <= n)。若存在ap1 = ap2 = ... = apm = x，且m > n / 2(0 <= pk < n, 1 <= k <= m)，则称x为A的主元素
示例：
A = (0, 5, 5, 3, 5, 7, 5, 5)
// 则5是主元素
B = (0, 5, 5, 3, 5, 1, 5, 7)
// 则B中没有主元素
假设A中的n个元素保存在⼀个⼀维数组中，请设计⼀个尽可能⾼效的算法，找出数组元素中的主元素。若存在主元素则输出该元素，否则输出-1
代码实现：
var list : [Int] = [0, 5, 5, 3, 4, 5, 5, 7, 5];
var count = 1;
var key = list[0];
for i in 1..<list.count {
if(key == list[i]){
count += 1;
continue;
}
if(count > 1){
count -= 1;
continue;
}
key = list[i];
count = 1;
}
if(count > 0){
count = 0;
for i in 0..<list.count {
if(key != list[i]){
continue;
}
count += 1;
}
}
if(count > list.count / 2){
print("主元素：\(key)");
}
else{
print("主元素：-1");
}
第一次循环，找到有可能成为主元素的候选元素
遍历数组，遇到相同元素
count + 1，不同元素count -1如果
count <= 1，更换候选元素，初始化count = 1
count > 0表示存在候选元素，进入第二次循环，找到候选元素出现的次数候选元素出现次数超过数组长度的一半，则该元素为主元素
2.7 删除链表中绝对值相等的结点
⽤单链表保存m个整数，结点的结构为(data, link)，且|data| <= n（n为正整数）
现在要去设计⼀个时间复杂度尽可能⾼效的算法，对于链表中的data绝对值相等的结点，仅保留第⼀次出现的结点，⽽删除其余绝对值相等的结点
示例：
原链表：A = {21, -15, 15, -7, 15}
删除后：A = {21, -15, -7}
代码实现：
public struct LinkedList<Element: Comparable>{
func deleteEqualNode(n : Int){
var arr : [Int] = Array(repeating: 0, count: n + 1);
var prior = _head;
var ptr = _head?.next;
while(ptr != nil){
let data = abs(ptr?.data as! Int);
if(arr[data] == 0){
arr[data] = 1;
prior = ptr;
}
else{
prior?.next = ptr?.next;
}
ptr = ptr?.next;
}
}
}
创建空间为
n + 1的数组，全部用0填充遍历链表，以当前元素绝对值作为索引，查找数组中的值
0：表示第⼀次出现，将数组该索引位置标记为11：表示已经出现过，从链表中删除该结点
若有收获，就点个赞吧
0 人点赞
