考研笔记

板子：链表就地逆置

带头结点：把头结点摘下来当成空表，原来的结点一个个头插回去，顺序就反了。不带头结点：用三个指针，边走边把 next 反过来。

代码

void reverseList(LinkList L) {              // 带头结点：摘下来逐个头插
    LNode *p = L->next, *q;                 // p：还没处理的第一个结点
    L->next = NULL;                         // 头结点先断开，当成一个空表
    while (p != NULL) {
        q = p->next;                        // 先记住 p 的后继，改完 p->next 就找不到了
        p->next = L->next;                  // 把 p 头插到 L 后面
        L->next = p;
        p = q;                              // 处理下一个
    }
}
 
LNode *reverseNoHead(LNode *first) {        // 不带头结点：三指针，返回新的第一个结点
    LNode *pre = NULL, *p = first, *r;      // pre：已经逆置好的那部分的第一个结点
    while (p != NULL) {
        r = p->next;                        // 保存后继
        p->next = pre;                      // 把 p 的指针反过来
        pre = p;                            // pre、p 一起后移
        p = r;
    }
    return pre;                             // 循环结束时 p 为 NULL，pre 是原来的最后一个结点
}

复杂度：时间 ，空间 。

任何一个结点都能当「头结点」

reverseList(p) 会把 p 后面的部分逆置，p 本身不动。 2019 年的链表重排就是这么用的：先找到中点 p，再逆置 p 后面的半段。见 链表重排。

易错点

  • 改 p->next 之前先保存后继。这是链表题里最常见的断链错误。
  • 带头结点的版本一开始必须写 L->next = NULL。漏了的话，第一个头插的结点会执行 p->next = L->next，也就是 p->next = p，自己指向自己。
  • 如果题目只要求逆序输出、不要求改链表，可以递归到表尾再输出，或者借助栈。

链接

反向链接