使用OC实现单链表：创建、删除、插入、查询、遍历、反转、合并、判断相交、求成环入口

一、概念

链表和数组都是一种线性结构，数组有序存储的，链表是无序存储的。

数组中的每一个元素地址是递增或者递减的关系，链表的每一个节点的地址没有此规律，它们是通过指针的指向连接起来。

链表种类：单链表、双向链表、循环链表、双向循环链表

单链表：一个数据域data、一个后继指针域next。也即：上一个节点指向下一个节点，尾节点指向空。

双向链表：一个数据域data、一个前驱指针域previous、一个后继指针域next。也即：上一个节点和下一个节点互相指向，尾节点指向空。

循环链表：一个数据域data、一个后继指针域next。也即：上一个节点指向下一个节点，尾节点指向首节点。

双向循环链表：一个数据域data、一个前驱指针域previous、一个后继指针域next。也即：上一个节点和下一个节点互相指向，尾节点和首节点也互相指向。

如图：

二、实现 

1、定义节点：

//  SingleLinkNode.h
//  LinkListDemo
//  Created by 夏远全 on 2019/9/24.

#import <Foundation/Foundation.h>

NS_ASSUME_NONNULL_BEGIN

//单链表节点
@interface SingleLinkNode : NSObject
@property (nonatomic, assign) int data; //数据域
@property (nonatomic, strong, nullable) SingleLinkNode *next;//后继指针域
+(instancetype)constructNodeWithData:(int)data;
@end

//  SingleLinkNode.m
//  LinkListDemo
//  Created by 夏远全 on 2019/9/24.

#import "SingleLinkNode.h"

@implementation SingleLinkNode

+(instancetype)constructNodeWithData:(int)data{
    SingleLinkNode *node = [[SingleLinkNode alloc] init];
    node.data = data;
    node.next = nil;
    return node;
}
@end

2、构建链表（遍历打印方法在下面）

//1、构建一个单链表
SingleLinkNode *head = [[SingleLinkNode alloc] init];
SingleLinkNode *node1 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node2 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node3 = [SingleLinkNode constructNodeWithData:];
head.next = node1;
node1.next = node2;
node2.next = node3;
[FuncontionHelper printFromHeadWithNode:head printPrefixText:@"构造单链表为"];

-- ::10.363408+ LinkList[:] 构造单链表为：->->

3、插入节点

3-1：在头部插入

//在头部插入节点
+(void)insetNodeAfterHead:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }

    /*
    //方式一：先用一个临时节点记录头结点的下一个节点，然后将头结点指向新节点，新节点再指向临时节点
    if (headNode.next == nil) {
        headNode.next = newNode;
    }else{
        SingleLinkNode *tempNode = headNode.next;
        headNode.next = newNode;
        newNode.next = tempNode;
    }
    */

    //方式二：先把新节点指向头结点的下一个节点，再让头结点指向新节点(比较常用)
    if (headNode.next == nil) {
        headNode.next = newNode;
    }else{
        newNode.next = headNode.next;
        headNode.next = newNode;
    }
}

SingleLinkNode *node4 = [SingleLinkNode constructNodeWithData:];
[FuncontionHelper insetNodeAfterHead:node4 headNode:head];
[FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表头部插入节点4后"];

-- ::10.363732+ LinkList[:] 在单链表头部插入节点4后：->->->3   //1->2->3

3-2：在尾部插入

//在尾部插入节点
+(void)insetNodeAfterTail:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }
    if (headNode.next == nil) {
        headNode.next = newNode;
    }
    else{
        SingleLinkNode *pNode = headNode;
        while (pNode.next != nil) { //遍历到尾部
            pNode = pNode.next;
        }
        pNode.next = newNode;
    }
}

SingleLinkNode *node5 = [SingleLinkNode constructNodeWithData:];
[FuncontionHelper insetNodeAfterTail:node5 headNode:head];
[FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表尾部插入节点5后"];

-- ::10.363816+ LinkList[:] 在单链表尾部插入节点5后：->->->->5   //4->1->2->3

3-3：在指定位置插入

//在指定位置插入节点
+(void)insetNodeAtIndex:(int)k node:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }

    if (headNode.next == nil) {
        headNode.next = newNode;
    }
    else{
        SingleLinkNode *pNode = headNode;
        int i = ;
        while (i < k && pNode.next != nil) {
            pNode = pNode.next;
            i++;
        }
        newNode.next = pNode.next;
        pNode.next = newNode;
    }
}

SingleLinkNode *node6 = [SingleLinkNode constructNodeWithData:];
[FuncontionHelper insetNodeAtIndex: node:node6 headNode:head];
[FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表第2个位置插入节点6后"];

-- ::10.363872+ LinkList[:] 在单链表第2个位置插入节点6后：->->->->->5  //4->1->2->3->5

4、删除节点

//单链表：删除第k个位置的节点
+(SingleLinkNode *)deleteNodeAtIndex:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next || k==) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有要删除的第%d个节点!",k]);
        return nil;
    }

    SingleLinkNode *pNode = headNode;
    SingleLinkNode *p = pNode;//移动指针
    int i = ;
    while (pNode.next != nil && i < k) {
        p = pNode;
        pNode = pNode.next;
        i++;
    }
    if (pNode != nil) {
        p.next = p.next.next;
        return pNode;
    }

    NSLog(@"%@",[NSString stringWithFormat:@"没有要删除的第%d个节点!",k]);
    return nil;
}

SingleLinkNode *deleteNode = [FuncontionHelper deleteNodeAtIndex: headNode:head];
NSString *prefixText = [NSString stringWithFormat:@"删除第1个位置的节点%d后单链表为",deleteNode.data];
[FuncontionHelper printFromHeadWithNode:head printPrefixText:prefixText];

-- ::10.363902+ LinkList[:] 删除第1个位置的节点4后单链表为：->->->->5  //4->6->1->2->3->5

5、查询节点

5-1：正向查询

//单链表：查询第k个位置的节点
+(SingleLinkNode *)queryNodeIndex:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到第%d个节点!",k]);
        return nil;
    }

    SingleLinkNode *pNode = headNode.next;
    int i = ;
    while (pNode != nil && i < k) {
        pNode = pNode.next;
        i++;
    }
    if (pNode != nil) {
        return pNode;
    }
    NSLog(@"%@",[NSString stringWithFormat:@"没有查询到第%d个节点!",k]);
    return nil;
}

SingleLinkNode *node_x = [FuncontionHelper queryNodeIndex: headNode:head];
if (node_x) NSLog(@"查询到第1个结点的值是：%d",node_x.data); 

-- ::10.363916+ LinkList[:] 查询到第1个结点的值是：6     //6->1->2->3->5

5-2：反向查询（两次遍历法、快慢指针法）

//单链表：查询倒数第k个位置的节点
+(SingleLinkNode *)queryNodeCountdown:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
        return nil;
    }

    /*
    //方式一：两次遍历法：第一次遍历获取链表总长度L，第二次遍历区间为[1,L-k+1]即可
    int L = 0;
    SingleLinkNode *pNode = headNode.next;
    while (pNode != nil) {
        pNode = pNode.next;
        L++;
    }
    if (k > L) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
        return nil;
    }
    pNode = headNode.next;
    for (int i=1; i<L-k+1; i++) {
       pNode = pNode.next;
    }
    return pNode;
    */

    //方式二：使用快慢指针法，快指针先走k步，然后快慢指针一起走，等到快指针结束时，慢指针所在位置就是目标节点
    SingleLinkNode *quickNode = headNode.next;
    SingleLinkNode *slowNode = headNode.next;
    int i = ;
    while (quickNode != nil && i<k) {
        quickNode = quickNode.next;
        i++;
    }
    if (i == k) {
        while (quickNode != nil && slowNode != nil) {
            quickNode = quickNode.next;
            slowNode  = slowNode.next;
        }
        if (quickNode == nil && slowNode != nil) {
            return slowNode;
        }else{
            NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
            return nil;
        }
    }
    NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
    return nil;
}

SingleLinkNode *node_y = [FuncontionHelper queryNodeCountdown: headNode:head];
if (node_y) NSLog(@"查询到倒数第1个结点的值是：%d",node_y.data);

-- ::10.363934+ LinkList[:] 查询到倒数第1个结点的值是： //6->1->2->3->5

6、遍历链表

6-1：正向遍历

//正序遍历链表
+(NSArray<NSNumber *>*)printFromHeadWithNode:(SingleLinkNode *)headNode printPrefixText:(NSString *)text {

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    SingleLinkNode *pNode = headNode.next;
    NSMutableArray *items = [NSMutableArray array];
    while (pNode!= nil) {
        [items addObject:@(pNode.data)];
        pNode = pNode.next;
    }
    NSLog(@"%@：%@",text,[items componentsJoinedByString:@"->"]);
    return items;
}

6-2：反向遍历（递归法、指针法）

//倒序遍历链表
+(NSArray<NSNumber *>*)printFromTailWithNode:(SingleLinkNode *)headNode{

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //方式一：递归打印
    /*
    NSMutableArray *items = [NSMutableArray array];
    if (headNode.next != nil) {
        headNode = headNode.next;
        [self printFromTailWithNode:headNode];
        [items addObject:@(headNode.data)];
    }
    return items;
    */

    //方式二：遍历指针偏移，每次遍历完一次后，要记录最后一个节点，然后将遍历指针移动到开头重新开始，与记录的最后一个节点作比较
    NSMutableArray *items = [NSMutableArray array];
    SingleLinkNode *pNode = headNode;
    SingleLinkNode *lastNode = nil;
    while (pNode != nil && lastNode != pNode) {
        pNode = pNode.next;
        if (pNode.next == nil || pNode.next == lastNode) {
            lastNode = pNode;
            pNode = headNode;
            [items addObject:@(lastNode.data)];
        }
    }
    return items;
}

NSArray *items = [FuncontionHelper printFromTailWithNode:head];
NSLog(@"链表倒序遍历：%@",[items componentsJoinedByString:@"、"]);

-- ::10.363962+ LinkList[:] 链表倒序遍历：、、、、6    //6->1->2->3->5

7、反转链表

//反转链表
+(SingleLinkNode *)reverseWithNode:(SingleLinkNode *)headNode{

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //采用头结点插入的方式反转
    SingleLinkNode *p = headNode.next; ///定义遍历指针
    SingleLinkNode *newHead = [[SingleLinkNode alloc] init]; ///定义反转后头结点
    while (p != nil) {
        SingleLinkNode *temp = p.next;///记录下一个节点
        p.next = newHead.next; ///当前节点指向新头结点的下一个节点
        newHead.next = p; ///更换新头结点指向当前节点
        p = temp; ///移动p指针
    }
    return newHead;
}

SingleLinkNode *newHead = [FuncontionHelper reverseWithNode:head];
[FuncontionHelper printFromHeadWithNode:newHead printPrefixText:@"将单链表反转后"];

-- ::10.363999+ LinkList[:] 将单链表反转后：->->->->6   //6->1->2->3->5

8、合并有序链表

//单链表：两个有序链表合成一个新的有序链表
+(SingleLinkNode *)combineWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode {

    //判空处理
    if (!headNode || !headNode.next) {
        return otherNode;
    }
    if (!otherNode || !otherNode.next) {
        return headNode;
    }

    //一起开始扫描
    SingleLinkNode *p1 = headNode.next;
    SingleLinkNode *p2 = otherNode.next;
    SingleLinkNode *newHead = [[SingleLinkNode alloc] init];//定义一个新头结点
    while (p1 != nil && p2 != nil) {
        if (p1.data > p2.data) {
            otherNode.next = p2.next; //移动otherNode头结点指向当前节点的下一个节点
            p2.next = nil;//将当前节点从otherNode链表断掉
            [self insetNodeAfterTail:p2 headNode:newHead];//将当前节点插入到新链表newHead的尾部
            p2 = otherNode.next;//获取otherNode链表的下一点节点
        }else{
            headNode.next = p1.next;
            p1.next = nil;
            [self insetNodeAfterTail:p1 headNode:newHead];
            p1 = headNode.next;
        }
    }

    //处理没有扫描结束的链表
    while (p1 != nil) {
        headNode.next = p1.next;
        p1.next = nil;
        [self insetNodeAfterTail:p1 headNode:newHead];//尾节点插入
        p1 = headNode.next;
    }
    while (p2 != nil) {
        otherNode.next = p2.next;
        p2.next = nil;
        [self insetNodeAfterTail:p2 headNode:newHead];//尾节点插入
        p2 = otherNode.next;
    }
    return newHead;
}

SingleLinkNode *head1 = [[SingleLinkNode alloc] init];
SingleLinkNode *node11 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node22 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node33 = [SingleLinkNode constructNodeWithData:];
head1.next = node11;
node11.next = node22;
node22.next = node33;
[FuncontionHelper printFromHeadWithNode:head1 printPrefixText:@"构造第一个有序单链表为:"];

SingleLinkNode *otherHead = [[SingleLinkNode alloc] init];
SingleLinkNode *node44 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node55 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node66 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node77 = [SingleLinkNode constructNodeWithData:];
otherHead.next = node44;
node44.next = node55;
node55.next = node66;
node66.next = node77;
[FuncontionHelper printFromHeadWithNode:otherHead printPrefixText:@"构造第二个有序单链表为:"];

SingleLinkNode *combieHeadNode = [FuncontionHelper combineWithNode:head1 otherNode:otherHead];
[FuncontionHelper printFromHeadWithNode:combieHeadNode printPrefixText:@"合并后的有序新链表为:"];

-- ::10.364037+ LinkList[:] 构造第一个有序单链表为:：->->
-- ::10.364067+ LinkList[:] 构造第二个有序单链表为:：->->->
-- ::10.364098+ LinkList[:] 合并后的有序新链表为:：->->->->->->

9、判断两个链表是否相交

//单链表：判断两个链表是否相交 (只能是某一个链表的尾节点与另一链表的某一个节点相交)
+(BOOL)intersectWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode {

    //判空处理
    if (!headNode || !headNode.next || !otherNode || !otherNode.next) {
        return NO;
    }

    //思路：分别获取两个链表的长度，判断谁的链表更长，链表更长的先走完相差的步数，然后齐步走
    SingleLinkNode *p1 = headNode.next;
    SingleLinkNode *p2 = otherNode.next;
    int L1 = ;
    int L2 = ;
    while (p1 != nil) {
        L1 ++;
        p1 = p1.next;
    }
    while (p2 != nil) {
        L2 ++;
        p2 = p2.next;
    }
    p1 = headNode.next;  //将p1遍历指针移动到首节点
    p2 = otherNode.next; //将p2遍历指针移动到首节点
    int i=;
    if (L1 > L2) {
        while (i < L1-L2 && p1 != nil) { //p1先走
            p1 = p1.next;
            i++;
        }
    }else{
        while (i < L2-L1 && p2 != nil) { //p2先走
            p2 = p2.next;
            i++;
        }
    }
    if (i == ABS(L1-L2)) {
        while (p1 != nil && p2 != nil) { //p1、p2齐步走
            if(p1.next == p2.next) return YES; //相交
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    return NO;
}

SingleLinkNode *head2 = [[SingleLinkNode alloc] init];
SingleLinkNode *node111 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node222 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node333 = [SingleLinkNode constructNodeWithData:];
head2.next = node111;
node111.next = node222;
node222.next = node333;
[FuncontionHelper printFromHeadWithNode:head2 printPrefixText:@"单链表1"];

SingleLinkNode *otherHead2 = [[SingleLinkNode alloc] init];
SingleLinkNode *node444 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node555 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node666 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node777 = [SingleLinkNode constructNodeWithData:];
otherHead2.next = node444;
node444.next = node555;
node555.next = node666;
node666.next = node777;
node777.next = node222;//指向链表1的node222节点
[FuncontionHelper printFromHeadWithNode:otherHead2 printPrefixText:@"单链表2"];

BOOL isIntersect = [FuncontionHelper intersectWithNode:head2 otherNode:otherHead2];
NSLog(@"单链表1和单链表2是否相交：%@", isIntersect ? @"相交" : @"不相交");

-- ::10.364154+ LinkList[:] 单链表1：->->
-- ::10.364189+ LinkList[:] 单链表2：->->->->->
-- ::10.364201+ LinkList[:] 单链表1和单链表2是否相交：相交  //相交点从3开始

10、判断链表是否构成环，如果成环，求出环的入口节点

//单链表：判断链表是否构成环，如果成环，返回构成环的那个节点
+(SingleLinkNode *)circleWithNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //思路：采用快慢指针法
    //快指针先走两步，慢指针走一步，如果成环，必然重合。走到第一次重合的地点后，重新设置一个指针p指向头结点，并与慢节点同步伐齐步走,
    //走到第二次相遇的地方，即为构成环的节点
    SingleLinkNode *quick = headNode.next;
    SingleLinkNode *slow  = headNode.next;
    SingleLinkNode *p     = headNode.next;
    while (quick != nil && slow != nil) {
        quick = quick.next.next;
        slow = slow.next;
        if (quick == slow) { //第一次重合，结束循环
            break;
        }
    }
    while (p != nil && slow != nil) {
        p = p.next;
        slow = slow.next;
        if (p == slow) { //第二次重合，找到成环的入口节点
            return p;
        }
    }
    return nil;
}

SingleLinkNode *head3 = [[SingleLinkNode alloc] init];
SingleLinkNode *node1111 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node2222 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node3333 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node4444 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node5555 = [SingleLinkNode constructNodeWithData:];
SingleLinkNode *node6666 = [SingleLinkNode constructNodeWithData:];
head3.next = node1111;
node1111.next = node2222;
node2222.next = node3333;
node3333.next = node4444;
node4444.next = node5555;
node5555.next = node6666;
node6666.next = node2222;
        /*
              1 -> 3 -> 4 -> 5
                    \       /
                     7 -  6
        */
SingleLinkNode *circleNode = [FuncontionHelper circleWithNode:head3];
NSLog(@"链表是否成环：%@, 成环的入口节点是%d:", circleNode != nil ? @"成环" : @"不成环", circleNode.data);

-- ::10.364225+ LinkList[:] 链表是否成环：成环, 成环的入口节点是3:

三、源码

FuncontionHelper.h

//
//  FuncontionHelper.h
//  LinkList
//
//  Created by 夏远全 on 2019/9/25.
//

#import <Foundation/Foundation.h>
#import "SingleLinkNode.h"
#import "SingleCycleLinkNode.h"
#import "DoubleLinkNode.h"
#import "DoubleCycleLinkNode.h"

NS_ASSUME_NONNULL_BEGIN

@interface FuncontionHelper : NSObject

//单链表：在头部插入节点
+(void)insetNodeAfterHead:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode;

//单链表：在尾部插入节点
+(void)insetNodeAfterTail:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode;

//单链表：在指定位置插入节点
+(void)insetNodeAtIndex:(int)k node:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode;

//单链表：删除第k个位置的节点
+(SingleLinkNode *)deleteNodeAtIndex:(int)k headNode:(SingleLinkNode *)headNode;

//单链表：查询第k个位置的节点
+(SingleLinkNode *)queryNodeIndex:(int)k headNode:(SingleLinkNode *)headNode;

//单链表：查询倒数第k个位置的节点
+(SingleLinkNode *)queryNodeCountdown:(int)k headNode:(SingleLinkNode *)headNode;

//单链表：正序遍历链表
+(NSArray<NSNumber *>*)printFromHeadWithNode:(SingleLinkNode *)headNode printPrefixText:(NSString *)text;

//单链表：倒序遍历链表
+(NSArray<NSNumber *>*)printFromTailWithNode:(SingleLinkNode *)headNode;

//单链表：反转链表
+(SingleLinkNode *)reverseWithNode:(SingleLinkNode *)headNode;

//单链表：两个有序链表合成一个新的有序链表
+(SingleLinkNode *)combineWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode;

//单链表：判断两个链表是否相交
+(BOOL)intersectWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode;

//单链表：判断链表是否构成环，如果成环，返回构成环的那个节点
+(SingleLinkNode *)circleWithNode:(SingleLinkNode *)headNode;

@end

NS_ASSUME_NONNULL_END

FuncontionHelper.m

//
//  FuncontionHelper.m
//  LinkList
//
//  Created by 夏远全 on 2019/9/25.
//

#import "FuncontionHelper.h"

@implementation FuncontionHelper

//在头部插入节点
+(void)insetNodeAfterHead:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }

    /*
    //方式一：先用一个临时节点记录头结点的下一个节点，然后将头结点指向新节点，新节点再指向临时节点
    if (headNode.next == nil) {
        headNode.next = newNode;
    }else{
        SingleLinkNode *tempNode = headNode.next;
        headNode.next = newNode;
        newNode.next = tempNode;
    }
    */

    //方式二：先把新节点指向头结点的下一个节点，再让头结点指向新节点(比较常用)
    if (headNode.next == nil) {
        headNode.next = newNode;
    }else{
        newNode.next = headNode.next;
        headNode.next = newNode;
    }
}

//在尾部插入节点
+(void)insetNodeAfterTail:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }
    if (headNode.next == nil) {
        headNode.next = newNode;
    }
    else{
        SingleLinkNode *pNode = headNode;
        while (pNode.next != nil) {
            pNode = pNode.next;
        }
        pNode.next = newNode;
    }
}

//在指定位置插入节点
+(void)insetNodeAtIndex:(int)k node:(SingleLinkNode *)newNode headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode) {
        return;
    }

    if (headNode.next == nil) {
        headNode.next = newNode;
    }
    else{
        SingleLinkNode *pNode = headNode;
        int i = ;
        while (i < k && pNode.next != nil) {
            pNode = pNode.next;
            i++;
        }
        newNode.next = pNode.next;
        pNode.next = newNode;
    }
}

//单链表：删除第k个位置的节点
+(SingleLinkNode *)deleteNodeAtIndex:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next || k==) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有要删除的第%d个节点!",k]);
        return nil;
    }

    SingleLinkNode *pNode = headNode;
    SingleLinkNode *p = pNode;//移动指针
    int i = ;
    while (pNode.next != nil && i < k) {
        p = pNode;
        pNode = pNode.next;
        i++;
    }
    if (pNode != nil) {
        p.next = p.next.next;
        return pNode;
    }

    NSLog(@"%@",[NSString stringWithFormat:@"没有要删除的第%d个节点!",k]);
    return nil;
}

//单链表：查询第k个位置的节点
+(SingleLinkNode *)queryNodeIndex:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到第%d个节点!",k]);
        return nil;
    }

    SingleLinkNode *pNode = headNode.next;
    int i = ;
    while (pNode != nil && i < k) {
        pNode = pNode.next;
        i++;
    }
    if (pNode != nil) {
        return pNode;
    }
    NSLog(@"%@",[NSString stringWithFormat:@"没有查询到第%d个节点!",k]);
    return nil;
}

//单链表：查询倒数第k个位置的节点
+(SingleLinkNode *)queryNodeCountdown:(int)k headNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
        return nil;
    }

    /*
    //方式一：两次遍历法：第一次遍历获取链表总长度L，第二次遍历区间为[1,L-k+1]即可
    int L = 0;
    SingleLinkNode *pNode = headNode.next;
    while (pNode != nil) {
        pNode = pNode.next;
        L++;
    }
    if (k > L) {
        NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
        return nil;
    }
    pNode = headNode.next;
    for (int i=1; i<L-k+1; i++) {
       pNode = pNode.next;
    }
    return pNode;
    */

    //方式二：使用快慢指针法，快指针先走k步，然后快慢指针一起走，等到快指针结束时，慢指针所在位置就是目标节点
    SingleLinkNode *quickNode = headNode.next;
    SingleLinkNode *slowNode = headNode.next;
    int i = ;
    while (quickNode != nil && i<k) {
        quickNode = quickNode.next;
        i++;
    }
    if (i == k) {
        while (quickNode != nil && slowNode != nil) {
            quickNode = quickNode.next;
            slowNode  = slowNode.next;
        }
        if (quickNode == nil && slowNode != nil) {
            return slowNode;
        }else{
            NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
            return nil;
        }
    }
    NSLog(@"%@",[NSString stringWithFormat:@"没有查询到倒数第%d个节点!",k]);
    return nil;
}

//正序遍历链表
+(NSArray<NSNumber *>*)printFromHeadWithNode:(SingleLinkNode *)headNode printPrefixText:(NSString *)text {

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    SingleLinkNode *pNode = headNode.next;
    NSMutableArray *items = [NSMutableArray array];
    while (pNode!= nil) {
        [items addObject:@(pNode.data)];
        pNode = pNode.next;
    }
    NSLog(@"%@：%@",text,[items componentsJoinedByString:@"->"]);
    return items;
}

//倒序遍历链表
+(NSArray<NSNumber *>*)printFromTailWithNode:(SingleLinkNode *)headNode{

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //方式一：递归打印
    /*
    NSMutableArray *items = [NSMutableArray array];
    if (headNode.next != nil) {
        headNode = headNode.next;
        [self printFromTailWithNode:headNode];
        [items addObject:@(headNode.data)];
    }
    return items;
    */

    //方式二：遍历指针偏移，每次遍历完一次后，要记录最后一个节点，然后将遍历指针移动到开头重新开始，与记录的最后一个节点作比较
    NSMutableArray *items = [NSMutableArray array];
    SingleLinkNode *pNode = headNode;
    SingleLinkNode *lastNode = nil;
    while (pNode != nil && lastNode != pNode) {
        pNode = pNode.next;
        if (pNode.next == nil || pNode.next == lastNode) {
            lastNode = pNode;
            pNode = headNode;
            [items addObject:@(lastNode.data)];
        }
    }
    return items;
}

//反转链表
+(SingleLinkNode *)reverseWithNode:(SingleLinkNode *)headNode{

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //采用头结点插入的方式反转
    SingleLinkNode *p = headNode.next; ///定义遍历指针
    SingleLinkNode *newHead = [[SingleLinkNode alloc] init]; ///定义反转后头结点
    while (p != nil) {
        SingleLinkNode *temp = p.next;///记录下一个节点
        p.next = newHead.next; ///当前节点指向新头结点的下一个节点
        newHead.next = p; ///更换新头结点指向当前节点
        p = temp; ///移动p指针
    }
    return newHead;
}

//单链表：两个有序链表合成一个新的有序链表
+(SingleLinkNode *)combineWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode {

    //判空处理
    if (!headNode || !headNode.next) {
        return otherNode;
    }
    if (!otherNode || !otherNode.next) {
        return headNode;
    }

    //一起开始扫描
    SingleLinkNode *p1 = headNode.next;
    SingleLinkNode *p2 = otherNode.next;
    SingleLinkNode *newHead = [[SingleLinkNode alloc] init];//定义一个新头结点
    while (p1 != nil && p2 != nil) {
        if (p1.data > p2.data) {
            otherNode.next = p2.next; //移动otherNode头结点指向当前节点的下一个节点
            p2.next = nil;//将当前节点从otherNode链表断掉
            [self insetNodeAfterTail:p2 headNode:newHead];//将当前节点插入到新链表newHead的尾部
            p2 = otherNode.next;//获取otherNode链表的下一点节点
        }else{
            headNode.next = p1.next;
            p1.next = nil;
            [self insetNodeAfterTail:p1 headNode:newHead];
            p1 = headNode.next;
        }
    }

    //处理没有扫描结束的链表
    while (p1 != nil) {
        headNode.next = p1.next;
        p1.next = nil;
        [self insetNodeAfterTail:p1 headNode:newHead];//尾节点插入
        p1 = headNode.next;
    }
    while (p2 != nil) {
        otherNode.next = p2.next;
        p2.next = nil;
        [self insetNodeAfterTail:p2 headNode:newHead];//尾节点插入
        p2 = otherNode.next;
    }
    return newHead;
}

//单链表：判断两个链表是否相交 (只能是某一个链表的尾节点与另一链表的某一个节点相交)
+(BOOL)intersectWithNode:(SingleLinkNode *)headNode otherNode:(SingleLinkNode *)otherNode {

    //判空处理
    if (!headNode || !headNode.next || !otherNode || !otherNode.next) {
        return NO;
    }

    //思路：分别获取两个链表的长度，判断谁的链表更长，链表更长的先走完相差的步数，然后齐步走
    SingleLinkNode *p1 = headNode.next;
    SingleLinkNode *p2 = otherNode.next;
    int L1 = ;
    int L2 = ;
    while (p1 != nil) {
        L1 ++;
        p1 = p1.next;
    }
    while (p2 != nil) {
        L2 ++;
        p2 = p2.next;
    }
    p1 = headNode.next;  //将p1遍历指针移动到首节点
    p2 = otherNode.next; //将p2遍历指针移动到首节点
    int i=;
    if (L1 > L2) {
        while (i < L1-L2 && p1 != nil) { //p1先走
            p1 = p1.next;
            i++;
        }
    }else{
        while (i < L2-L1 && p2 != nil) { //p2先走
            p2 = p2.next;
            i++;
        }
    }
    if (i == ABS(L1-L2)) {
        while (p1 != nil && p2 != nil) { //p1、p2齐步走
            if(p1.next == p2.next) return YES; //相交
            p1 = p1.next;
            p2 = p2.next;
        }
    }
    return NO;
}

//单链表：判断链表是否构成环，如果成环，返回构成环的那个节点
+(SingleLinkNode *)circleWithNode:(SingleLinkNode *)headNode {

    //判空处理
    if (!headNode || !headNode.next) {
        return nil;
    }

    //思路：采用快慢指针法
    //快指针先走两步，慢指针走一步，如果成环，必然重合。走到第一次重合的地点后，重新设置一个指针p指向头结点，并与慢节点同步伐齐步走,
    //走到第二次相遇的地方，即为构成环的节点
    SingleLinkNode *quick = headNode.next;
    SingleLinkNode *slow  = headNode.next;
    SingleLinkNode *p     = headNode.next;
    while (quick != nil && slow != nil) {
        quick = quick.next.next;
        slow = slow.next;
        if (quick == slow) { //第一次重合，结束循环
            break;
        }
    }
    while (p != nil && slow != nil) {
        p = p.next;
        slow = slow.next;
        if (p == slow) { //第二次重合，找到成环的入口节点
            return p;
        }
    }
    return nil;
}

@end

main方法

//
//  main.m
//  LinkList
//
//  Created by 夏远全 on 2019/9/25.
//

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

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        //1、构建一个单链表
        SingleLinkNode *head = [[SingleLinkNode alloc] init];
        SingleLinkNode *node1 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node2 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node3 = [SingleLinkNode constructNodeWithData:];
        head.next = node1;
        node1.next = node2;
        node2.next = node3;
        [FuncontionHelper printFromHeadWithNode:head printPrefixText:@"构造单链表为"];

        //2、从单链表中插入节点
        SingleLinkNode *node4 = [SingleLinkNode constructNodeWithData:];
        [FuncontionHelper insetNodeAfterHead:node4 headNode:head];
        [FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表头部插入节点4后"];

        SingleLinkNode *node5 = [SingleLinkNode constructNodeWithData:];
        [FuncontionHelper insetNodeAfterTail:node5 headNode:head];
        [FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表尾部插入节点5后"];

        SingleLinkNode *node6 = [SingleLinkNode constructNodeWithData:];
        [FuncontionHelper insetNodeAtIndex: node:node6 headNode:head];
        [FuncontionHelper printFromHeadWithNode:head printPrefixText:@"在单链表第2个位置插入节点6后"];

        //3、删除节点
        SingleLinkNode *deleteNode = [FuncontionHelper deleteNodeAtIndex: headNode:head];
        NSString *prefixText = [NSString stringWithFormat:@"删除第1个位置的节点%d后单链表为",deleteNode.data];
        [FuncontionHelper printFromHeadWithNode:head printPrefixText:prefixText];

        //4、查询节点
        SingleLinkNode *node_x = [FuncontionHelper queryNodeIndex: headNode:head];
        if (node_x) NSLog(@"查询到第1个结点的值是：%d",node_x.data);

        SingleLinkNode *node_y = [FuncontionHelper queryNodeCountdown: headNode:head];
        if (node_y) NSLog(@"查询到倒数第1个结点的值是：%d",node_y.data);

        //5、倒序遍历
        NSArray *items = [FuncontionHelper printFromTailWithNode:head];
        NSLog(@"链表倒序遍历：%@",[items componentsJoinedByString:@"、"]);

        //6、反转链表
        SingleLinkNode *newHead = [FuncontionHelper reverseWithNode:head];
        [FuncontionHelper printFromHeadWithNode:newHead printPrefixText:@"将单链表反转后"];

        //7、合并单链表
        SingleLinkNode *head1 = [[SingleLinkNode alloc] init];
        SingleLinkNode *node11 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node22 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node33 = [SingleLinkNode constructNodeWithData:];
        head1.next = node11;
        node11.next = node22;
        node22.next = node33;
        [FuncontionHelper printFromHeadWithNode:head1 printPrefixText:@"构造第一个有序单链表为:"];

        SingleLinkNode *otherHead = [[SingleLinkNode alloc] init];
        SingleLinkNode *node44 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node55 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node66 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node77 = [SingleLinkNode constructNodeWithData:];
        otherHead.next = node44;
        node44.next = node55;
        node55.next = node66;
        node66.next = node77;
        [FuncontionHelper printFromHeadWithNode:otherHead printPrefixText:@"构造第二个有序单链表为:"];

        SingleLinkNode *combieHeadNode = [FuncontionHelper combineWithNode:head1 otherNode:otherHead];
        [FuncontionHelper printFromHeadWithNode:combieHeadNode printPrefixText:@"合并后的有序新链表为:"];

        //8、判断相交
        SingleLinkNode *head2 = [[SingleLinkNode alloc] init];
        SingleLinkNode *node111 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node222 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node333 = [SingleLinkNode constructNodeWithData:];
        head2.next = node111;
        node111.next = node222;
        node222.next = node333;
        [FuncontionHelper printFromHeadWithNode:head2 printPrefixText:@"单链表1"];

        SingleLinkNode *otherHead2 = [[SingleLinkNode alloc] init];
        SingleLinkNode *node444 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node555 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node666 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node777 = [SingleLinkNode constructNodeWithData:];
        otherHead2.next = node444;
        node444.next = node555;
        node555.next = node666;
        node666.next = node777;
        node777.next = node222;//指向链表1的node222节点
        [FuncontionHelper printFromHeadWithNode:otherHead2 printPrefixText:@"单链表2"];

        BOOL isIntersect = [FuncontionHelper intersectWithNode:head2 otherNode:otherHead2];
        NSLog(@"单链表1和单链表2是否相交：%@", isIntersect ? @"相交" : @"不相交");

        //8、判断成环
        SingleLinkNode *head3 = [[SingleLinkNode alloc] init];
        SingleLinkNode *node1111 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node2222 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node3333 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node4444 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node5555 = [SingleLinkNode constructNodeWithData:];
        SingleLinkNode *node6666 = [SingleLinkNode constructNodeWithData:];
        head3.next = node1111;
        node1111.next = node2222;
        node2222.next = node3333;
        node3333.next = node4444;
        node4444.next = node5555;
        node5555.next = node6666;
        node6666.next = node2222;
        /*
              1 -> 3 -> 4 -> 5
                    \       /
                     7 -  6
        */
        SingleLinkNode *circleNode = [FuncontionHelper circleWithNode:head3];
        NSLog(@"链表是否成环：%@, 成环的入口节点是%d:", circleNode != nil ? @"成环" : @"不成环", circleNode.data);

    }
    return ;
}