老青菜

剑指offer-链表倒序

2017-01-23

题目

定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。

分析

假如有链表 {1,2,3,4,5}。我们可以这样操作:

  1. 声明节点a,节点b。a指向头节点,b指向头节点后面的节点,即需要调整的节点。
  2. 准备调整节点b,先记录b后面的节点为tmp。
  3. 把节点b放在链表头部,即 b->next = a。
  4. 更新当前头节点a,即 a = b。
  5. 更新需要调整的节点b,即 b = tmp。
  6. 重复上面步骤,知道没有需要调整的节点为止,即b == NULL。

实现

ZHNode *reverseLinklist(ZHNode *hNode) {
    //链表为空,或者只有一个节点
    if (hNode == NULL || hNode->next == NULL) {
        return hNode;
    }
    ZHNode *preNode = hNode;
    ZHNode *adjustNode = hNode->next;
    hNode->next = NULL;//断开头节点引用
    while (adjustNode) {
        //记录需要调整的节点的 后面节点,即adjustNode->next指针
        ZHNode *tmpNode = adjustNode->next;
        //把后面节点放在链表头部,即 next 指向当前节点
        adjustNode->next = preNode;
        //记录当前头部
        preNode = adjustNode;
        //记录下次要 调整的 节点
        adjustNode = tmpNode;
    }
    return preNode;
}

添加测试代码:

//mock 链表
ZHNode *hNode = malloc(sizeof(ZHNode));
hNode->data = 1;
ZHNode *lastNode = hNode;
for (int i=2; i<=10; i++) {
    ZHNode *nextNode = malloc(sizeof(ZHNode));
    nextNode->data = i;
    lastNode->next = nextNode;
    lastNode = nextNode;
}
//反转
ZHNode *tmpNode = reverseLinklist(hNode);
//输出结果
while (tmpNode) {
    printf("%d,", tmpNode->data);
    tmpNode = tmpNode->next;
}

//output
10,9,8,7,6,5,4,3,2,1,
使用支付宝打赏
使用微信打赏

若你觉得我的文章对你有帮助,欢迎点击上方按钮对我打赏

扫描二维码,分享此文章