算法&单链表反转（三）

主要介绍链表的简单用法以及单链表反转。网上的实现有很多，使用 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;
}

其实套路都是相似的，拿出纸与笔，自己比划几下就知道了。

自此，我感觉单链表反转的重点都差不多了。

你说呢？

参考文章

单向链表反转（倒置）问题