链表算法

作者: 点滴86 | 来源:发表于2024-07-15 00:02 被阅读0次

数据结构 - 单向链表及相关算法
19 删除链表的倒数第 N 个结点
头条-手撕代码
单链表
大厂面试系列(七)：数据结构与算法等
Java实现每日一道算法面试题（20）：leecode23 合并
总结
2018-06-07
链表类算法题汇总
如何设计一个内存缓存库

单链表反转

@class DMLinkModel;

@interface DMLinkModel : NSObject

@property (nonatomic, strong) DMLinkModel *next;

@property (nonatomic, strong) NSString *data;

@end

@implementation DMLinkModel

@end
@interface DMDemo : NSObject

@end

@implementation DMDemo

- (void)test
{
        DMLinkModel *tmpLinkModel = [self normalNodeLink];
        NSLog(@"正常链表");
        NSLog(@"链表反转前");
        [self printLink:tmpLinkModel];
        NSLog(@"链表反转后");
        DMLinkModel *resultLinkModel = [self reverseLink:tmpLinkModel];
        [self printLink:resultLinkModel];
}
// 链表反转
- (DMLinkModel *)reverseLink:(DMLinkModel *)linkModel
{
    DMLinkModel *preLinkModel = linkModel;
    DMLinkModel *curLinkModel = preLinkModel.next;
    DMLinkModel *nextLinkModel = nil;
    preLinkModel.next = nil;
    while (curLinkModel != nil) {
        nextLinkModel = curLinkModel.next;
        curLinkModel.next = preLinkModel;
        preLinkModel = curLinkModel;
        curLinkModel = nextLinkModel;
    }
    
    return preLinkModel;
}

- (DMLinkModel *)normalNodeLink
{
    DMLinkModel *tmpLink = [[DMLinkModel alloc] init];
    tmpLink.data = @"a";
    
    DMLinkModel *bLink = [[DMLinkModel alloc] init];
    bLink.data = @"b";
    tmpLink.next = bLink;
    
    DMLinkModel *cLink = [[DMLinkModel alloc] init];
    cLink.data = @"c";
    bLink.next = cLink;
    
    DMLinkModel *dLink = [[DMLinkModel alloc] init];
    dLink.data = @"d";
    cLink.next = dLink;
    
    DMLinkModel *eLink = [[DMLinkModel alloc] init];
    eLink.data = @"e";
    eLink.next = nil;
    
    dLink.next = eLink;
    
    return tmpLink;
}

- (void)printLink:(DMLinkModel *)linkModel
{
    DMLinkModel *tmpLinkModel = linkModel;
    NSMutableString *tmpStr = [[NSMutableString alloc] initWithString:@""];
    while (tmpLinkModel != nil) {
        [tmpStr appendFormat:@" %@", tmpLinkModel.data];
        tmpLinkModel = tmpLinkModel.next;
    }
    NSLog(@"%@", tmpStr);
}

@end

链表中环的检测

@class DMLinkModel;

@interface DMLinkModel : NSObject

@property (nonatomic, strong) DMLinkModel *next;

@property (nonatomic, strong) NSString *data;

@end

@implementation DMLinkModel

@end
@interface DMDemo : NSObject

@end

@implementation DMDemo

- (void)test
{
    DMLinkModel *normalLink = [self normalNodeLink];
    NSLog(@"链表");
    [self printLink:normalLink];
    if ([self isLoop:normalLink]) {
        NSLog(@"链表中有环");
    } else {
        NSLog(@"链表中没有环");
    }
    
    DMLinkModel *loopLink = [self loopNodeLink];
    NSLog(@"链表");
    if ([self isLoop:loopLink]) {
        NSLog(@"链表中有环");
    } else {
        NSLog(@"链表中没有环");
    }
}

// 链表中环的检测
- (BOOL)isLoop:(DMLinkModel *)linkModel
{
    if (linkModel == nil) {
        return NO;
    }
    // 初始时，慢指针从头开始走一步
    DMLinkModel *slowModel = linkModel.next;
    if (slowModel == nil) {
        return NO;
    }
    
    // 初始时，快指针从头开始走两步
    DMLinkModel *fastModel = slowModel.next;
    while (slowModel != nil && fastModel != nil) {
        if (slowModel == fastModel) {
            return YES;
        }
        
        // 慢指针每次走一步
        slowModel = slowModel.next;
        
        // 快指针每次走两步
        fastModel = fastModel.next;
        if (fastModel == nil) {
            return NO;
        }
        fastModel = fastModel.next;
    }
    return NO;
}

- (DMLinkModel *)normalNodeLink
{
    DMLinkModel *tmpLink = [[DMLinkModel alloc] init];
    tmpLink.data = @"a";
    
    DMLinkModel *bLink = [[DMLinkModel alloc] init];
    bLink.data = @"b";
    tmpLink.next = bLink;
    
    DMLinkModel *cLink = [[DMLinkModel alloc] init];
    cLink.data = @"c";
    bLink.next = cLink;
    
    DMLinkModel *dLink = [[DMLinkModel alloc] init];
    dLink.data = @"d";
    cLink.next = dLink;
    
    DMLinkModel *eLink = [[DMLinkModel alloc] init];
    eLink.data = @"e";
    eLink.next = nil;
    
    dLink.next = eLink;
    
    return tmpLink;
}

- (DMLinkModel *)loopNodeLink
{
    DMLinkModel *tmpLink = [[DMLinkModel alloc] init];
    tmpLink.data = @"a";
    
    DMLinkModel *bLink = [[DMLinkModel alloc] init];
    bLink.data = @"b";
    tmpLink.next = bLink;
    
    DMLinkModel *cLink = [[DMLinkModel alloc] init];
    cLink.data = @"c";
    bLink.next = cLink;
    
    DMLinkModel *dLink = [[DMLinkModel alloc] init];
    dLink.data = @"d";
    cLink.next = dLink;
    
    DMLinkModel *eLink = [[DMLinkModel alloc] init];
    eLink.data = @"e";
    eLink.next = cLink;
    
    dLink.next = eLink;
    
    return tmpLink;
}

- (void)printLink:(DMLinkModel *)linkModel
{
    DMLinkModel *tmpLinkModel = linkModel;
    NSMutableString *tmpStr = [[NSMutableString alloc] initWithString:@""];
    while (tmpLinkModel != nil) {
        [tmpStr appendFormat:@" %@", tmpLinkModel.data];
        tmpLinkModel = tmpLinkModel.next;
    }
    NSLog(@"%@", tmpStr);
}

两个有序链表的合并

@class DMLinkModel;

@interface DMLinkModel : NSObject

@property (nonatomic, strong) DMLinkModel *next;

@property (nonatomic, strong) NSString *data;

@end

@implementation DMLinkModel

@end
@interface DMDemo : NSObject

@end

@implementation DMDemo

- (void)test
{
    DMLinkModel *oddLink = [self oddNumberLink];
    NSLog(@"有序链表一");
    [self printLink:oddLink];
    
    DMLinkModel *evenLink = [self evenNumberLink];
    NSLog(@"有序链表二");
    [self printLink:evenLink];
    
    NSLog(@"有序链表合并之后");
    DMLinkModel *tmpLink = [self mergeLinkOne:oddLink linkTwo:evenLink];
    [self printLink:tmpLink];
}

// 两个有序链表的合并
- (DMLinkModel *)mergeLinkOne:(DMLinkModel *)oneLink linkTwo:(DMLinkModel *)twoLink
{
    DMLinkModel *headLink = nil;
    DMLinkModel *tmpLink = nil;
    DMLinkModel *tmpOneLink = oneLink;
    DMLinkModel *tmpTwoLink = twoLink;
    
    while (tmpOneLink != nil && tmpTwoLink != nil) {
        if ([tmpOneLink.data integerValue] > [tmpTwoLink.data integerValue]) {
            DMLinkModel *linkModel = [[DMLinkModel alloc] init];
            linkModel.data = tmpTwoLink.data;
            linkModel.next = nil;
            if (headLink == nil) {
                headLink = linkModel;
                tmpLink = headLink;
            }
            tmpLink.next = linkModel;
            tmpLink = linkModel;
            tmpTwoLink = tmpTwoLink.next;
        } else {
            DMLinkModel *linkModel = [[DMLinkModel alloc] init];
            linkModel.data = tmpOneLink.data;
            linkModel.next = nil;
            if (headLink == nil) {
                headLink = linkModel;
                tmpLink = headLink;
            }
            tmpLink.next = linkModel;
            tmpLink = linkModel;
            tmpOneLink = tmpOneLink.next;
        }
    }
    
    while (tmpOneLink != nil) {
        DMLinkModel *linkModel = [[DMLinkModel alloc] init];
        linkModel.data = tmpOneLink.data;
        linkModel.next = nil;
        if (headLink == nil) {
            headLink = linkModel;
            tmpLink = headLink;
        }
        tmpLink.next = linkModel;
        tmpLink = linkModel;
        tmpOneLink = tmpOneLink.next;
    }
    
    while (tmpTwoLink != nil) {
        DMLinkModel *linkModel = [[DMLinkModel alloc] init];
        linkModel.data = tmpTwoLink.data;
        linkModel.next = nil;
        if (headLink == nil) {
            headLink = linkModel;
            tmpLink = headLink;
        }
        tmpLink.next = linkModel;
        tmpLink = linkModel;
        tmpTwoLink = tmpTwoLink.next;
    }
    
    return headLink;
}

- (DMLinkModel *)oddNumberLink
{
    DMLinkModel *tmpLink = [[DMLinkModel alloc] init];
    tmpLink.data = @"1";
    
    DMLinkModel *bLink = [[DMLinkModel alloc] init];
    bLink.data = @"3";
    tmpLink.next = bLink;
    
    DMLinkModel *cLink = [[DMLinkModel alloc] init];
    cLink.data = @"5";
    bLink.next = cLink;
    
    DMLinkModel *dLink = [[DMLinkModel alloc] init];
    dLink.data = @"7";
    cLink.next = dLink;
    
    DMLinkModel *eLink = [[DMLinkModel alloc] init];
    eLink.data = @"9";
    eLink.next = nil;
    
    dLink.next = eLink;
    
    return tmpLink;
}

- (DMLinkModel *)evenNumberLink
{
    DMLinkModel *tmpLink = [[DMLinkModel alloc] init];
    tmpLink.data = @"2";
    
    DMLinkModel *bLink = [[DMLinkModel alloc] init];
    bLink.data = @"4";
    tmpLink.next = bLink;
    
    DMLinkModel *cLink = [[DMLinkModel alloc] init];
    cLink.data = @"6";
    bLink.next = cLink;
    
    DMLinkModel *dLink = [[DMLinkModel alloc] init];
    dLink.data = @"8";
    cLink.next = dLink;
    
    DMLinkModel *eLink = [[DMLinkModel alloc] init];
    eLink.data = @"10";
    eLink.next = nil;
    
    dLink.next = eLink;
    
    return tmpLink;
}

- (void)printLink:(DMLinkModel *)linkModel
{
    DMLinkModel *tmpLinkModel = linkModel;
    NSMutableString *tmpStr = [[NSMutableString alloc] initWithString:@""];
    while (tmpLinkModel != nil) {
        [tmpStr appendFormat:@" %@", tmpLinkModel.data];
        tmpLinkModel = tmpLinkModel.next;
    }
    NSLog(@"%@", tmpStr);
}

@end

数据结构 - 单向链表及相关算法
单向链表链表常见算法链表反转
19 删除链表的倒数第 N 个结点
题目：给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。自行解答：算法思路：其实算法是链表...
头条-手撕代码
[toc] 图算法以及最短路径算法树算法手写LRU 排序算法链表算法
单链表
单链表一些相关的算法集锦，单链表的算法可以提高逻辑能力。反转链表最基本的链表的题目，很简单的迭代操作，需要注意...
大厂面试系列(七)：数据结构与算法等
数据结构和算法链表链表，常见的面试题有写一个链表中删除一个节点的算法、单链表倒转、两个链表找相交的部分，这个一...
Java实现每日一道算法面试题（20）：leecode23 合并
1.算法题目合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。示例: 2.算法思路算法思...
总结
Android篇数据结构与算法顺序表 - ArrayList源码链表 - 单向链表、双向链表 - LinkedL...
2018-06-07
算法笔记 1 大O算法 1：O(运算次数)：表示运算最糟糕情况下运算时间，表示算法时间的增速 2数组链表在链表...
链表类算法题汇总
算法题目中常考察的链表操作无非以下几种：链表反转链表合并寻找链表中点寻找链表倒数第 K 个节点删除链表节...
如何设计一个内存缓存库
双向链表 + LRU淘汰算法 + 线程安全双向链表的设计用OC来设计双向链表（不是循环链表）单个节点整个链...