链表算法

• 单链表反转

@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