数据结构-链表

链表原理

参考(https://blog.csdn.net/jianyuerensheng/article/details/51585200)

• 链表是一种数据结构，和数组同级
• 链表在进行循环遍历时效率不高，但是插入和删除时优势明显
• 节点（Node）组成的，一个链表拥有不定数量的节点
• 数据在内存中存储是不连续的
• 节点（Node）是由一个需要储存的对象及对下一个节点的引用组成的

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

@interface Node : NSObject
@property (nonatomic, strong) id value;
@property (nonatomic, retain) Node * next;
@end

@interface LinkList : NSObject<NSMutableCopying>
@property (nonatomic, strong) Node *head;
@property (nonatomic, assign) NSUInteger length;


- (BOOL)addObject:(id)value;
- (BOOL)insertObject:(id)value atIndex:(NSUInteger)index;
- (BOOL)removeObject:(id)value;
- (BOOL)removeObjectAtIndex:(NSUInteger)index;
- (BOOL)removeAll;
- (id)objectAtIndex:(NSUInteger)index;
- (void)enumWithBlock:(void(^)(id value))block;

@end

NS_ASSUME_NONNULL_END

#import "LinkList.h"

@implementation Node

@end

@implementation LinkList



 - (id)mutableCopyWithZone:(NSZone *)zone
{
    LinkList * link = [LinkList allocWithZone:zone];
    return link;
}

- (NSUInteger)length
{
    Node *node = self.head;
    int count = 0;
    while (node) 
    {
        node = node.next;
        count ++;
    }
    return count;
}

- (Node *)getLastNode
{
    Node *node = self.head;
    while (node) 
    {
        if (node.next == nil)
        {
            break;
        }
        node = node.next;
    }
    return node;
}

- (BOOL)addObject:(id)value
{
    Node *newNode = [[Node alloc] init];
    newNode.value = value;
    
    if (self.head == nil)
    {
        self.head = newNode;
        return YES;
    }
    
    Node *node = [self getLastNode];
    if (node == nil)
    {
        return NO;
    }
    node.next = newNode;
    return YES;
}

- (BOOL)insertObject:(id)value atIndex:(NSUInteger)index
{
    if (index < 0)
    {
        return NO;
    }
    
    if (index >= self.length)
    {
        [self addObject:value];
        return YES;
    }
    
    Node *node = [self objectAtIndex:index];
    Node *newNode = [[Node alloc] init];
    
    Node *preNext = node.next;
    newNode.value = value;
    newNode.next = preNext;
    
    node.next = newNode;
    
    return YES;
}

- (BOOL)removeObject:(id)value
{
    Node *node = self.head;
    Node *preNode = self.head;
    
    while (node != nil && node.value != value)
    {
        preNode = node;
        node = node.next;
    }
    
    if (node == nil)
    {
        return NO;
    }
    
    preNode.next = node.next;
    node = nil;
    
    return YES;
}

- (BOOL)removeObjectAtIndex:(NSUInteger)index
{
    if (index >= self.length)
    {
        return NO;
    }
    
    Node *node = self.head;
    Node *preNode = self.head;
    
    NSUInteger count = 0;
    
    while (index != count)
    {
        preNode = node;
        node = node.next;
        count ++;
    }
    
    if (node == nil) 
    {
        return NO;
    }
    
    preNode.next = node.next;
    node = nil;
    
    return NO;
}

- (BOOL)removeAll
{
    while (self.head)
    {
        Node *node = self.head;
        Node *next = self.head.next;
        
        self.head = next;
        node = nil;
    }
    return YES;
}

- (id)objectAtIndex:(NSUInteger)index
{
    if (index >= self.length)
    {
        return nil;
    }
    
    Node *node = self.head;
    int count = 0;
    while (count == index) 
    {
        node = node.next;
        count ++;
    }
    return node;
}

/*
 链表反转
 调整指针的指向，反转后链表的头结点是原始链表的尾节点
 */
- (void)reversalLinkList
{
    Node *node = self.head;
    Node *pPrev = nil;
    
    while (node != nil)
    {
        Node *next = node.next;

        if (next == nil)
        {
            self.head = node;
        }
        node.next = pPrev;
        pPrev = node;
        node = next;
    }
}

- (void)enumWithBlock:(void (^)(id _Nonnull))block
{
    if (!block)
    {
        return;
    }
    Node *node = self.head;
    
    while (node)
    {
        block(node.value);
        node = node.next;
    }
}
/*
 查找单链表的中间节点
 采用快慢指针的方式查找单链表的中间节点，快指针一次走两步，慢指针一次走一步，当快指针走完时，慢指针刚好到达中间节点。
 */
- (Node *)cutInMiddle
{
    Node * node = self.head;
    Node *mid = self.head;
    
    while (node)
    {
        if (node.next != nil && node.next.next == nil)
        {
            break;
        }
        node = node.next.next;
        mid = mid.next;
    }
    
    return mid;
}

/*
 查找倒数第k个元素
 采用两个指针P1,P2，P1先前移K步，然后P1、P2同时移动，当p1移动到尾部时，P2所指位置的元素即倒数第k个元素 。
 */
- (Node *)getNodeFromlast:(NSUInteger)index
{
    Node *node = self.head;
    Node *targetNode = nil;
    
    NSUInteger count = 0;
    while (node)
    {
        
        if (count < index)
        {
            count ++;
        }
        else
        {
            targetNode = node;
        }
        node = node.next;
    }
    return targetNode;
}

//  删除链表中的重复节点
- (void)deleteDuplecate
{
    Node *node = self.head;
    
    while (node)
    {
        Node *p = node;
        
        while (p.next)
        {
            if (node.value == p.next.value)
            {
                p.next = p.next.next;
            }
            else
            {
                p = p.next;
            }
        }
        p = p.next;
    }
}

//从尾到头输出单链表，采用递归方式实现
- (void)printLink:(Node *)head
{
    if (!head)
    {
        return;
    }
    
    NSLog(@"%@",head.value);
    if (head.next)
    {
        [self printLink:head.next];
    }
}

//判断链表是否有环，有环情况下找出环的入口节点
//判断链表是否有环，单向链表有环时，尾节点相同
- (BOOL)isLoop
{
    if (!self.head)
    {
        return NO;
    }
    Node *fast = self.head;
    Node *slow = self.head;
    
    while (fast && fast.next)
    {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow)
        {
            return YES;
        }
        
    }
    
    return !(fast == nil || fast.next == nil);
}

// 查找环入口
- (Node *)findLoopPort
{
    Node *fast = self.head;
    Node *slow = self.head;
    
    while (fast && fast.next)
    {
        fast = fast.next.next;
        slow = slow.next;
        if (fast == slow)
        {
            break;
        }
    
    }
    
    slow = self.head;
    
    while (slow != fast)
    {
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
}
@end

链表中环的问题扩展
参考（https://www.cnblogs.com/yorkyang/p/10876604.html）