#import <Foundation/Foundation.h>
#import "LCArray.h"

NS_ASSUME_NONNULL_BEGIN

@interface LCLinkArray : LCArray

@end

NS_ASSUME_NONNULL_END

#import "LCLinkArray.h"


@interface LCNode : NSObject
@property(nonatomic,strong)id       element;
@property(nonatomic,strong)LCNode * next;


/// 创建一个新的节点
/// @param element 节点元素
/// @param node 节点next指针
+(LCNode*)nodeWithElement:(id)element next:(LCNode*)node;

@end

@implementation LCNode

+(LCNode*)nodeWithElement:(id)element next:(LCNode*)node{
    LCNode*newNode = [[LCNode alloc] init];
    newNode.element = element;
    newNode.next = node;
    return newNode;
}

@end




@interface LCLinkArray()

@end


@implementation LCLinkArray{
    LCNode * _first;
}


- (void)add:(int)index element:(nonnull id)element {
    [self rangeCheckForAdd:index];
    
    if (index == 0) {
        _first = [LCNode nodeWithElement:element next:_first];
    }else{
        LCNode * preNode = [self nodeForIndex:index-1];
        preNode.next = [LCNode nodeWithElement:element next:preNode.next];
    }
    _size++;
}


- (void)clear {
    _first = nil;
    _size = 0;
}


- (nonnull id)get:(int)index {
    return [self nodeForIndex:index].element;
}


- (int)indexOf:(nonnull id)element {
    
    LCNode * node = _first;
    for (int i = 0; i<_size; i++) {
        if ([element isEqual:node.element]) {
            return i;
        }
        node = node.next;
    }
    
    return ELEMENT_NOT_FOUND;
}


- (nonnull id)remove:(int)index {
   
    [self rangeCheck:index];
    
    //first -> node0 -> node1 -> node2
    
    LCNode * node = _first;
    
    if (index == 0) {
        _first = _first.next;
    }else{
        LCNode * preNode = [self nodeForIndex:index-1];
        node = preNode.next;
        preNode.next = node.next;
    }
    _size--;
    return node.element;
}


- (nonnull id)set:(int)index element:(nonnull id)element {
    LCNode * node = [self nodeForIndex:index];
    id oldElement = node.element;
    node.element = element;
    return oldElement;
}


#pragma mark - 内部方法


/// 获取index位置的node对象
/// @param index 索引
-(LCNode*)nodeForIndex:(int)index{
    
    [self rangeCheck:index];
    
    LCNode * node = _first;
    for (int i=0; i<index; i++) {
        node = node.next;
    }
    return node;
}



-(NSString *)description{
    NSMutableString * des = [NSMutableString stringWithFormat:@"size=%d, [",_size];
    
    LCNode * node = _first;
    
    for (int i=0; i<_size; i++) {
        if (i!=0) {
            [des appendString:@", "];
        }
        
        [des appendFormat:@"%@",node.element];
                
        node = node.next;
    }
    
    [des appendString:@"]"];
    
    return des;
}
@end

bool Solution::hasCycle(ListNode *head) {
    
    //思路：快慢指针
    
    //空链表或链表只有一个节点时，返回false
    if (head == nullptr || head->next == nullptr) {
        return false;
    }
    
    
    //避免起始时两个指针指向相同
    ListNode* slow = head;          //慢指针指向首个节点
    ListNode* fast = head->next;    //快指针指向第二个节点
    
    
    while (fast!=nullptr && fast->next!=nullptr) {
        slow = slow->next;
        fast = fast->next->next;
        
        if (slow == fast) {
            return true;
        }
    }
    
    return false;
}

/// 递归方式实现反转链表逻辑
/// @param head 链表
ListNode* Solution::reverseList(ListNode* head){
    
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* newHead = reverseList(head->next);
    head->next->next = head;
    head->next = nullptr;
    return newHead;
}

/// 迭代方式实现反转链表逻辑
/// @param head 链表
ListNode* Solution::reverseList2(ListNode* head){
    
    if (head == nullptr || head->next == nullptr) return head;
    
    ListNode* newHead = nullptr;
    while (head != nullptr) {
        ListNode* tmp = head->next;
        head->next = newHead;
        
        newHead = head;
        head = tmp;
    }
   return newHead;
}

void Solution::deleteNode(ListNode* node){
    node->val  = node->next->val;
    node->next = node->next->next;
}