美文网首页
算法题之--《反转链表》

算法题之--《反转链表》

作者: 忧郁的小码仔 | 来源:发表于2019-09-15 15:59 被阅读0次

我们先从数组创建一个链表:

@interface ListNode : NSObject

@property (nonatomic, assign) NSInteger key;
@property (nonatomic, strong) ListNode *next;

@end

@interface List : NSObject

-(instancetype)initFromArr:(NSArray *)arr;

@end
@implementation ListNode
@end


@interface List()
@property (nonatomic, strong) ListNode *head;
@end

@implementation List

-(instancetype)initFromArr:(NSArray *)arr {
    
    self = [super init];
    
    if (self) {
        
        ListNode *preNode;
        
        for (NSNumber *value in arr) {
            if (_head == nil) {
                _head = [[ListNode alloc] init];
                _head.key = [value integerValue];
                preNode = _head;
            } else {
                ListNode *newNode = [[ListNode alloc] init];
                newNode.key = [value integerValue];
                preNode.next = newNode;
                preNode = newNode;
            }
        }
    }
    return self;
}

-(NSString *)description {
    NSMutableString *result = [NSMutableString string];
    ListNode *currentNode = self.head;
    while (currentNode != nil) {
        [result appendString:[NSString stringWithFormat:@"%lu -> ", currentNode.key]];
        currentNode = currentNode.next;
    }
    [result appendString:@"null"];
    return [result copy];
}

@end

测试下:

    List *list = [[List alloc] initFromArr:@[@(1), @(2), @(3), @(4), @(5)]];
    NSLog(@"%@", list);
2019-09-03 17:38:26.028129+0800 Algorithm[1880:1129933] 1 -> 2 -> 3 -> 4 -> 5 -> null

链表反转

例如,我们要反转下面这个链表:


链表反转

只要重复2的动作一直到cur移动到最后的null节点,反转就完成了。
示例代码:

-(void)reverse {
    
    ListNode *pre = nil;
    ListNode *cur = self.head;
    ListNode *next;
    
    while (cur != nil) {
        next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    
    self.head = pre;
}

测试:

    List *list = [[List alloc] initFromArr:@[@(1), @(2), @(3), @(4), @(5)]];
    [list reverse];
    NSLog(@"%@", list);
2019-09-03 17:40:46.705029+0800 Algorithm[1883:1130326] 5 -> 4 -> 3 -> 2 -> 1 -> null

相关文章

网友评论

      本文标题:算法题之--《反转链表》

      本文链接:https://www.haomeiwen.com/subject/zhahyctx.html