408统考数据结构真题（1）

缺乏、安全感 2022-09-11 05:24 94阅读 0赞

### 408统考数据结构真题（1） ###

*   *  题目描述
     *  问题分析
     *  代码实现

## 题目描述 ##

输入：给定一个单链表L = (L1, L2, L3…Ln)  
输出：L1, Ln, L2, Ln-1…  
要求：空间复杂度为O(1)，算法时间效率尽可能高。

## 问题分析 ##

根据题目描述，也就是将链表的前半部分和后半部分依次交替插入新表中。但由于单链表的单向链接，必须将后半部分逆置，那么整个题目的解决思路就是三个部分：  
（1）找到两个部分的节点；  
（2）逆置后半部分的链表；  
（3）合并链表。

## 代码实现 ##

这是笔者原创解法，没有加注解，后续会发详细分析。也许这个解法很复杂，恳请算法大牛不吝赐教。

# include <stdio.h>
    
    struct LinkNode {
        
      int data;
      struct LinkNode *next;
    };
    
    void initLinkList (struct LinkNode *&L) {
        
      int num;
      struct LinkNode *r, *s;
      L = new LinkNode;
      r = L;
      while (scanf("%d", &num) != EOF) {
        
        s = new LinkNode;
        s->data = num;
        r->next = s;
        r = s;
      }
      r->next = NULL;
    }
    
    void printLinkList (struct LinkNode *L) {
        
      struct LinkNode *r = L->next;
      while (r) {
        
        printf("%d\t", r->data);
        r = r->next;
      }
    }
    
    void destroyLinkList (struct LinkNode *&L) {
        
      struct LinkNode *r;
      while(L) {
        
        r = L->next;
        delete(L);
        L = r;
      }
    }
    
    void findCenterIndicator (struct LinkNode *L, struct LinkNode *&center) {
        
      struct LinkNode *p = L->next, *q = p;
      while(p) {
        
        if(p->next && p->next->next) {
        
          p = p->next->next;
          q = q->next;
        } else {
        
          break;
        }
      }
      if (!q) {
        
        center = NULL;
        printf("空表。\n");
      }
      else if (!q->next) {
        
        center = NULL;
        printf("\n请至少输入两个节点。\n");
      }
      else {
        
        center = q->next;
        q->next = NULL;
      }
    }
    
    void reverseLinkList (struct LinkNode *&L) {
        
      struct LinkNode *r = NULL, *p = L, *q;
      while (p) {
        
        q = p->next;
        p->next = r;
        r = p;
        p = q;
      }
      L = new LinkNode;
      L->next = r;
    }
    
    void mergeLinkList (struct LinkNode *L1, struct LinkNode *L2) {
        
      struct LinkNode *p = L1->next, *q = L2->next, *r, *s;
      while (p && q) {
        
        r = p->next;
        s = q->next;
        q->next = r;
        p->next = q;
        p = r;
        q = s;
      }
    }
    
    int main() {
        
      struct LinkNode *A, *cen;
      initLinkList(A);
      printLinkList(A);
      findCenterIndicator(A, cen);
      if (cen) {
        
        printf("\nfindCenterIndicator:%d\n", cen->data);
      }
      printf("reverseLinkList:");
      reverseLinkList(cen);
      printLinkList(cen);
      printf("\nmergeLinkList:\n");
      mergeLinkList(A, cen);
      printLinkList(A);
      destroyLinkList(A);
      destroyLinkList(cen);
      return 0;
    }