算法 | 就地逆置、双指针快速寻找中间节点

2019年真题

设线性表 L=(a1, a2, a3, ..., an-2, an-1, an) 采用带头节点的单链表保存，链表中的结点定义如下：(代码1) 设计一个空间复杂度为O(1) 且时间上尽可能高效的算法，重新排列 L 中的各结，得到线性表 L’=(a1, an, a2, an-1, a3, an-2, ...)。

// 代码1
// lang C
typedef struct node{
  int data;
  struct node*next;
} NODE;

算法思路

• 使用双指针找到链表的中间结点
• 对链表的后半部分进行就地逆置
• 然后与链表前半部分按题目要求混合

// 一些必要的工作
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
#define maxSize 20

typedef struct node{
  ElemType data; // 结点中的数据元素
  struct node*next; // 结点的后继指针
}NODE, *LinkList;

// 初始化带头链表的函数
LinkList InitLinkList(LinkList l){
  l = (NODE*)malloc(sizeof(NODE)); // 创建一个头指针
  l->next = NULL;
  NODE *s; // 创建一个临时变量，用于初始化每一个结点
  NODE *t = NULL; // 用于保存上一个结点 
  for(int i=1; i<=maxSize; i++){
    s = (NODE*)malloc(sizeof(NODE));
    s->data = i;
    s->next = NULL;
    if(t == NULL)
      l->next = s; // 用头指针指向第一个结点
     else
       t->next = s; //上一个结点的后继指针指向当前结点
      t = s; 
  }
  return l;
}

// 使用双指针寻找链表的中间结点
// p指针每次后移一个，q每次后移两个；
// 等到q移动到最后一个元素，此时p指向的就是链表的中间结点
LinkList FindMiddleElme(LinkList p, LinkList q){
  while(q->next != NULL){
    if((q->next->next) != NULL)
      q = q->next->next; // q 后移两个结点
     else
       q = q->next; // 当 q 的后两个结点为空时，则后移一个，防止指针越界
     p = p->next; // 每次循环 p 指针都后移一个 
  }
  return p; // 此时 p 指针指向链表的中间j结点
}

// 就地逆置链表函数
// 使用头插法
// 没啥好说的，头插法逆置
LinkList reverse(LinkList l){
  NODE *p, *s, *h;
  h = (NODE*)malloc(sizeof(NODE));
  p = l; 
  s = p->next;
  h->next = NULL; 
  while(p != NULL){
    p->next = h->next;
    h->next = p;
    p = s;
    if(p != NULL)
      s = p->next;
  }
  return h;
}

// 打印链表函数
// 遍历链表每一个结点并打印元素
void PrintList(LinkList l){
  NODE* s;
  s = l;
  while(s != NULL){
    printf("%d ", s->data);
    s = s->next;
  }
}

// 混合函数
// 规则：L’=(a1, an, a2, an-1, a3, an-2, ...)
// 按照后半部分链表，将后半部分链表的每一个结点插到前边链表中
LinkList mix(LinkList l, LinkList p){
  NODE *s, *r, *m;
  s = p->next; // s 为中间指针，指向为待插入的结点
  p = s->next; // 将 p 指针指向下一个待插入的结点
  m = l->next; // m为中间指针，指向为待插入结点的前驱
  r = m; // 将 r 指向链表头
  while(s->next != NULL){
    s->next = m->next; // 待插入结点的后继指向插入位的后继
    m->next = s; // 插入位的前驱指向 待插入结点
    m = s->next; // 插入位后移
    s = p; // 待插入结点后移
    p = s->next; // 将 p 指针指向下一个待插入的结点
  }  
  return r;
}

// 主函数
int main(){
  LinkList LL = InitLinkList(LL);
  LinkList p = LL->next;
  LinkList q = p;
  
  // 寻找中间结点
  p = FindMiddleElme(p, q);
  
  // 就地逆置链表后半部分
  p = reverse(p);
  
  // 混合链表
  q = mix(LL, p);
  
  // 打印链表
  PrintList(q);
  return 0;
}

运行结果