数据结构课后习题：Reversing Linked List

题目描述：

题目解读：

1、需要每K步进行反转，剩下少于K的子表不反转

2、需要考虑输入数据有非法值，即有些节点不在链表中

思路：

1、用地址addr作为key存储链表节点，C语言由于没有哈希表，直接用addr作为数组的下标。

2、完成链表节点的存储后，需要找出链表的头节点，这里需要用next值作为key，存储本节点是否是其他节点的下一个节点：具体为，如果通过next能找到合法的链表节点，则这个合法的链表节点就不可能是头结点，循环给每一个节点打上标记

3、为了处理有些节点不在链表的场景，需要对找出的头结点进行合法性校验：遍历该头结所连接的链表，查看是否能找到结尾。若能最后找到next为-1的节点，则证明找到了正确的头结点。

4、在进行k步反转时，需要重新计算链表的长度，用新计算的链表长度 / K 得到需要反转的次数

5、逆序输出采用堆栈实现

下面是自己的代码实现：

  1 #include <stdio.h>
  2 #include <string.h>
  3 
  4 #define NULL -1
  5 #define MAX_SIZE 100001
  6 typedef struct T_node * list;
  7 typedef struct T_node
  8 {
  9     int addr;
 10     int data;
 11     int next; 
 12     int valid;
 13 }node_t;
 14 
 15 int nextaddr[MAX_SIZE]; /* 存储下一个链表地址的空间 */
 16 node_t nodeBuf[MAX_SIZE] = {0}; /* 存储链表节点的空间 */
 17 //简易堆栈
 18 int top = -1;
 19 list stack[MAX_SIZE];
 20 #define pop(top)   ((top > -1) ? stack[top--] : 0)
 21 #define push(x, top)   (top != MAX_SIZE-1) ? stack[++top] = (x) : 0
 22 #define isempty(top)  ((top == -1) ? 1 : 0)
 23 #define gettop(top)   (isempty(top) != 1 ? stack[top] : 0)
 24 #define getnext(next) (next!=NULL ? &nodeBuf[(next)] :(list) 0)
 25 /*===============================================================*/
 26 
 27 list reverse_link(list L, int k, int revercnt)
 28 {   
 29     list ret = 0;
 30     list Rear = 0;
 31     int j = 0;
 32     for (j = 0; j < revercnt; j++)
 33     {
 34         int i = 0;
 35         /* 倒序的内容入栈 */
 36         while (L != 0 && i < k)
 37         {
 38             push(L, top);
 39             L = getnext(L->next);
 40             i++;
 41         }
 42         /* 第一次逆序，堆栈的第一个节点为头结点 */
 43         if (!isempty(top))
 44         {
 45             if (ret == 0)
 46                 ret = gettop(top);
 47             else
 48                 Rear->next = gettop(top)->addr; /* 记录上一次逆序后的尾部节点 */
 49         }
 50         /* 弹出节点，然后将该节点的下一个节点地址设置为堆栈的头结点 */
 51         while (!isempty(top))
 52         {
 53             list n = pop(top);
 54             if (isempty(top))
 55             {
 56                 if (L)
 57                     n->next = L->addr;
 58                 else
 59                     n->next = NULL;
 60                 Rear = n;
 61             }
 62             else
 63             {
 64                 list topnode = gettop(top);
 65                 n->next = topnode->addr;
 66             }
 67         
 68         }
 69     }
 70     return ret;
 71 }
 72 
 73 void printL(list L)
 74 {
 75     while (L)
 76     {
 77         if (L->next == NULL)
 78         {
 79             printf("%05d %d %d", L->addr, L->data, L->next);
 80             break;
 81         }
 82         else
 83             printf("%05d %d %05d
", L->addr, L->data, L->next);
 84         L = &nodeBuf[L->next];
 85     }
 86 }
 87 
 88 int main(void)
 89 {
 90     
 91     int addr, num, k, i = 0;
 92     list first = 0;
 93     scanf("%d %d %d",&addr, &num, &k);
 94     while (i < num)
 95     {
 96         node_t n = {0};
 97         n.next = NULL;
 98         scanf("%d %d %d", &n.addr, &n.data, &n.next);
 99         n.valid = 1;
100         nodeBuf[n.addr] = n;
101         if (n.next != NULL)
102             nextaddr[n.next] = 1;
103         else
104         {
105             nextaddr[n.addr] = 1;
106             first = &nodeBuf[n.addr];
107         } 
108         i++;
109     }
110     i = 0;
111     /* 找到链表的头结点  */
112     while (i < MAX_SIZE)
113     {
114         if (nodeBuf[i].valid && nextaddr[nodeBuf[i].addr] == 0)
115         {
116             list temp = &nodeBuf[i];
117             first = &nodeBuf[i];
118             num = 0;
119             while (temp && temp->valid)
120             {
121                 num++;
122                 temp = getnext(temp->next);
123             }/* 这里为了解决不在链表上的节点，所以要重新计算链表的节点数目  */
124             if (!temp)
125                 break;
126             else
127                 num = 0;/* 这里找到的不是第一个节点 */
128         }
129         i++;
130     }
131     list L = reverse_link(first, k, num/k);
132     printL(L);
133     return 0;
134 }

有什么更好的方式能找到正确的链表头结点呢？