链表反转与寻找中间结点

Contents

1. 1. 链表反转
   1. 1.1. 节点定义
   2. 1.2. 链表反转函数
2. 2. 寻找中间结点
   1. 2.1. 大致思想
   2. 2.2. 代码
3. 3. 测试与输出

　　前两天收到一个电话面试，期间问了一个关于链表的基础问题，而我竟然答错了。想想真是汗颜，一方面确实经验不足，有些紧张，另一方面也是太天真，总以为太过基础的内容不值花费太多时间。

　　其实作为在校生，面试官不会对你有多高的期望，最看重的就是你的基本素质，而我恰恰忽略了这方面的准备。虽然项目期间写了不少代码，但是Java本身就提供种类容器，很少遇到要自己去处理链表、排序之类的操作。所以乍一问及，也没来得及细想，就凭印象给出了一个错误答案。
　　
　　所以后来找了一些关于链表的常见问题，亡羊补牢一下。 　　

链表反转

　　所这个其实没有多少算法，凭直觉就能写出代码。考虑到笔试中使用C语言较多，所以这次用C来实现。说起来本科直接学的C++，与C的不同还是很明显的。

节点定义

链表名+next指针

#include <stdio.h>

typedef struct Node {
    char *name;
    struct Node *next;
} Node;

链表反转函数

　　所逻辑非常简单：保存原next到临时变量t,将next指向前一节点pre，更新pre为当前节点，最后将工作指针head指向t(原next)。

Node *reverseLink(Node *head) {
    Node *pre = 0, *t;
    while ( head){
        t = head->next;
        head->next = pre;
        pre = head;
        head = t;
    }
    return pre;
}

　　所需要注意的是返回值，链表反转以后，原head成为tail，tail成head。

寻找中间结点

　　所题目：给出head，定位中间节点，如果有两个，则给出前一个。

　　所第一反应是先遍历链表求得表长l，再从head遍历到l/2, 但是很明显这不是出题者想要的，于是我想到了之间看的如何检测链表存在环的解法（也许下次更新它的实现），使用fast and normal两种速度速度遍历，对这个问题非常适用。

大致思想

　　所normal指针每次走一步，fast每次走两人步，这样当fast到达链表尾时，normal位于链表中。

　　所另外需要稍微考虑下偶数个节点的情况的题目的要求。

代码

Node *findMid(Node *head){
    Node *fast=head, *normal = head;
    while(fast->next && fast->next->next){
        normal = normal->next;
        fast = fast->next->next;
    }
    return normal;
}

测试与输出

　　所以下是测试用的主函数及输出情况：

int main(int argc, char *argv[]) {
    Node node0={"E",0}, node1 = {"D", &node0}, node2 = {"C", &node1}, node3 = {"B", &node2}, head = {"A", &node3};
    Node *p = &head;
    while (p) {
        printf("%s", p->name);
        p = p->next;
    }
    printf("\n");

    printf("%s", findMid(&head)->name);
    printf("\n");

    Node *pNode = reverseLink(&head);
    p = pNode;
    while (p) {
        printf("%s", p->name);
        p = p->next;
    }
    printf("\n");
    return 0;
}

　　所输出 ：

ABCDE
C
EDCBA

　　所如果是偶数节点：

ABCD
B
DCBA

好的，面试官到底问了我什么问题呢？分析删除一个节点的时间性能。
我说是O(n)……但是我之前明明特意问了是给出节点内容还是地址，回答是地址（指针）,但我并没有意识到指针与内容的不同。只给�内容是O(n)没错，但是指针的话就没有查找的过程了，直接进入删除操作，所以答案是常数性能。

具体的操作，大二的《数据结构》课上就讲过，不过我是被告知答错时才想起来，已经晚了……