链表原理
参考(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）
网友评论