主要介绍链表的简单用法以及单链表反转。网上的实现有很多，使用 OC/C 来实现的没有几个。
一、链表的基本用法
链表是一种数据结构，从链表的流向性分为单链表与双向链表，当前简书主要记录的是单链表。
1.1 节点定义以及使用
节点的定义有主要有两种方式：结构体与类。当前已结构体为主，具体如下：
// 链表节点定义
typedef struct _node
{
// 数据
char* data;
// 下一个指针
struct _node* next;
} HGNode;
创建一个节点：
// 创建一个节点
- (HGNode*)createNode {
HGNode* node = (HGNode*)malloc(sizeof(HGNode));
// 现在是一个空的节点
return node;
}
1.2 链表创建
一个链表至少得有一个头结点，有且仅有一个。如果没有，则称为空链表。
一个简单的链表创建如下：
// 创建一个链表 返回一个头节点
- (HGNode*)createLink {
// 先创建一个 head 节点
HGNode* head = [self createNode];
{
// 数据
head->data = "head";
}
// 创建其它的节点
// 第一个节点
HGNode* node1 = [self createNode];
{
// 数据
node1->data = "A";
// 接到 head
head->next = node1;
}
// 第二个节点
HGNode* node2 = [self createNode];
{
// 数据
node2->data = "B";
// 接到 node1
node1->next = node2;
}
// 第三个节点
HGNode* node3 = [self createNode];
{
// 数据
node3->data = "C";
// 接到 node2
node2->next = node3;
}
return head;
}
这个链表的结构为：head-->A-->B-->C。head：头结点， A、B 与 C 为节点。
1.3 打印链表
对于一个链表来说，只要知道其头节点，就能访问到当前链表的所有节点。
// 打印
- (void)printWithLink:(HGNode*)headeLink {
NSMutableArray* tmpArrM = [NSMutableArray array];
// 遍历单列表
HGNode* tmpLink = headeLink;
while (tmpLink) {
[tmpArrM addObject:[NSString stringWithFormat:@"%s", tmpLink->data]];
tmpLink = tmpLink->next;
}
NSLog(@"链表打印: %@", [tmpArrM componentsJoinedByString:@"-->"]);
}
调用如下：
// 遍历链表
- (void)traverseLink {
HGNode* head = [self createLink];
// 打印
[self printWithLink:head];
}
打印结果：
链表打印: head-->A-->B-->C
1.4 节点删除
大概的思路是：遍历链表，找到删除节点的上一个节点与下一个节点，将上一个节点的 next 的值为下一个节点即可。但是需要考虑特殊情况，具体的代码：略。
二、单链表反转
一些很不好的实现方式，就直接跳过了，直接实现最经典的两种方式。 关于单链表图解，可以参考这篇文章【单向链表反转（倒置）问题】
2.1 方式一
其实单链表反转，是一个很老的话题，实现的方式也有很多的种，最经典的可能就是这种吧：
// 单链表反转
- (void)reverseWithLink:(HGNode*)headeLink {
// curP 是当前移动的节点
// pre 是 curP 的下一个节点
HGNode *curP, *pre;
// 当前节点为 头结点的下一个节点
curP = headeLink->next;
// 记录当前节点的上一个节点
HGNode* lastP = NULL;
// 开始遍历
while (curP) {
// 保留当前节点的写一个节点
pre = curP->next;
// 当前节点的下一个节点换成上一个节点(反转)
curP->next = lastP;
// 指针向前移动
lastP = curP;
curP = pre;
}
// 现在 lastP 就是之前节点的最后一个节点
headeLink->next = lastP;
}
自己拿出纸与笔，自己比划几下就知道是什么逻辑了。整个过程仅仅是遍历了一次。
调用方法：
// 单链表反转
- (void)reverse {
HGNode* head = [self createLink];
// 打印当前链表
[self printWithLink:head];
// 反转
[self reverseWithLink:head];
// 打印反转之后的链表
[self printWithLink:head];
}
打印结结果：
原始链表打印: head-->A-->B-->C
反转链表打印: head-->C-->B-->A
2.2 方式二 （递归）
上面的实现思路是从头节点一个一个的反转，接下来使用递归来实现一遍。递归的思路是先一口气的递归到最后一个节点，然后再一口气的反转。整个过程也是仅仅遍历一次。
代码实现如下：
// 单链表反转
- (void)reverseWithLink:(HGNode*)headeLink {
// 当前节点为 头结点的下一个节点
HGNode *curP = headeLink->next;
// 记录当前节点的上一个节点
HGNode* lastP = [self recursionReverseWithLink:curP];
// 现在 lastP 就是之前节点的最后一个节点
headeLink->next = lastP;
}
// 链表递归反转
// 这里不包括头节点就是将除了头节点的链表都反转
- (HGNode*)recursionReverseWithLink:(HGNode*)node {
// 说明 node 已经是最后一个节点
if (node->next == NULL) {
return node;
}
// 保留下一个节点
HGNode* preNode = node->next;
// 当前的先一个节点已经没有意义了, 因为要反转最好是先断开
node->next = NULL;
// 开始递归 preNode 节点
HGNode* reverseNode = [self recursionReverseWithLink:preNode];
// node变成最后一个节点
preNode->next = node;
// 这一个 reverseNode 就是 node 对应的最后的一个节点
return reverseNode;
}
其实套路都是相似的，拿出纸与笔，自己比划几下就知道了。
自此，我感觉单链表反转的重点都差不多了。
你说呢？
