链表之单链表逆序(反向)

运气真是太好了,两天内的三次笔试居然都考到对单链表进行反向!

要求像这样:对 -> -> 进行单链表反向操作,得到: -> ->

元素的定义如下:

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

操作方法总的来说很简单:

  1. 遍历链表的每一个节点P;
  2. 使节点P的next指向该节点的前面那个节点;

为了使节点P的next指向前面那个节点,所以得定义一个变量来保存前面那个节点。当然,在此之前还要进行一步的操作就是保存P节点的next,以便进行迭代。

具体实现代码可以是这样的:

Node* reverse(Node* root) {
  Node* new_root = NULL;            // 用来保存前面那个节点
  while (root) {                    // 遍历每个节点
    Node* next = root->next;        // 保存下一个节点
    root->next = new_root;          // 重新设置新的节点使其指向前一个节点
    new_root = root;                // 这两句:遍历指针后移
    root = next;
  }
  return new_root;                  // 新的头结点
}

完整的代码:

#include <stdio.h>

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

void print_list(Node* root) {
  while (root) {
    printf("%c ", root->data);
    root = root->next;
  }
  printf("\n");
}

Node* reverse(Node* root) {
  Node* new_root = 0;
  while (root) {
    Node* next = root->next;
    root->next = new_root;
    new_root = root;
    root = next;
  }
  return new_root;
}

int main() {
  Node d = { 'd', 0 };
  Node c = { 'c', &d };
  Node b = { 'b', &c };
  Node a = { 'a', &b };

  Node* root = &a;
  print_list(root);
  root = reverse(root);
  print_list(root);

  return 0;
}

参考

发表于:2015年07月27日 ,阅读量:393 ,标签:链表 · 数据结构

版权声明:若非特别注明,本站所有文章均为作者原创,转载请务必注明原文地址。